Posts

http://codeforces.com/contest/613/problem/B 题意：有n个技能，初始每个技能的level为a[i]，每个技能最大level为A(不妨称为满级技能)，设满级技能个数为maxnum，最小的技能level为minval，问如何将m个技能点分配到n个技能上使得cfmaxsum+cmminval (n<=1E5,a[i],A<=1E9,cf,cm<=1E3,m<=1E15)

http://www.lydsy.com/JudgeOnline/problem.php?id=3289 题意：中文题目，简单来说就是求某一区间内的逆序对数。 思路：逆序对数想到树状数组。不过写莫队转移的时候没弄明白。。。。大概是树状数组理解的还不够透彻。。。需要复习一下了。。。

There are two types of problems solvable by partial sum. 1.Problems which you are asked to answer some queries about the sum of a part of elements (without modify queries).

http://acm.hdu.edu.cn/showproblem.php?pid=5416 # 题意：给出一棵树（n<=1E5），定义二元函数函数f(u,v) (u可以等于v)表示节点u到节点v经过的路径的权值的异或和。给出q组查询（q<=10），每组一个s，问有多少对无序点对（u,v）满足f(u,v)=s. 思路：类似codeforces #340 div 2 E XOR and Favorite Number 先dfs，处理出从根节点都任意节点的异或前缀和。然后对于每个询问o(n)扫一遍，统计sum[i]^s出现多少次。 总的时间复杂度为O(Tqn);

http://acm.hdu.edu.cn/showproblem.php?pid=5327 题意：问给出的区间[a,b]中有多少个美丽数，美丽数的定义是所有数字都不相同，如123是，100不是，333也不是。 思路：预处理1..100000的美丽数，可以把每个数字拆开放在set里，比较set的size和位数来实现。 然后用前缀和。

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3693 题意： n+2个人取吃饭，每人w元，每k个人可以少付一个人的钱，问最后两个教练每人要付多少钱。

http://codeforces.com/contest/373/problem/C 题意：n个袋鼠，每个袋鼠的size为a[i]，一只袋鼠的size至少是另一只两倍时才能将它装下，被装下的袋鼠不能再装别的袋鼠且不能被看见。问能看见的袋鼠最少是多少。 思路：贪心。最多有n/2个袋鼠被装下。先排序，然后贪心即可。

http://acm.hdu.edu.cn/showproblem.php?pid=4638 题意：给定一个序列，序列由1-N个元素全排列而成，求任意区间连续的段数。例如序列2,3,5,6,9就是三段(2, 3) (5, 6)(9)。 思路：增加一个元素，如果它两边的元素都出现了，那么段数-1（相当于把两段连接起来合并成了一段），如果两边元素都没有出现，那么段数+1.反过来，减少一个元素时，如果两边元素都出现了，俺么段数+1（相当于把完整的一段断开成两段），如果两边元素都没有出现，那么段数-1.操作可以O(1)完成。。。上莫队。 因为id大小最大才100000，所以判断某个元素是否出现开一个100000大小的布尔数组即可（我竟然傻逼得去用set….然后华丽丽得TLE了2333）

http://codeforces.com/contest/614/problem/C # 题意：给一个多边形和多边形外一定点，多边形绕定点旋转，问多边形扫过的面积。 思路：简单计算几何，找到多边形距离定点的最大和最小距离R和r，答案就是(R^2-R^2)*PI 需要注意的是：最大距离一定是从某点上取得，但是最小距离可能不在顶点上，而在某条边上。

写了几道莫队，总结下。 目前只会区间莫队。。树上莫队以后再补。 莫队算法学习

https://ac.2333.moe/Problem/view.xhtml?id=1457 题意：求一段区间内数字个数的立方和。 思路：由于一共才1E5，而数字1E9，所以先离散化，再莫队，类似小z的袜子。 注意 ：%lld会WA，要用%I64d

http://acm.hdu.edu.cn/showproblem.php?pid=5145 题意：有n个女孩，编号1..n，第i个女孩在第a[i]个教室，m次访问，每次访问编号[L,R]的女孩，处于同一个教室的女孩一次只能访问一个，问有多少种访问方案。两个不同的方案当且仅当访问的顺序有所不同。

http://codeforces.com/contest/617/problem/E 题意：给出n个数，m个查询，每个查询给定l,r，问在区间【l,r】内，有多少对i,j，满足i^(i+1)^(i+2)^…^j的值为给定的常数k.

http://acm.hdu.edu.cn/showproblem.php?pid=5213 题意：n个数，m个查询，每个查询由4个数l1,r1,l2,r2构成，询问分别从[l1,r1]和[l2,r2]中各取一个数，和为给定的常数k的方案数。

http://codeforces.com/contest/220/problem/B 题意：n个数，m个查询区间，对于每一个区间[l,r]输出区间中cnt[x]==x的数的个数。 # 思路：首先，a[i]很大。。。但是n最大才1e5…每个a[i]最多出现1E5次。。所以对于大于1E5的a[i]对答案没有贡献。其次，上莫队算法。

http://codeforces.com/problemset/problem/86/D # 题意：Ks为区间内s的数目，求区间[L,R]之间所有KsKss的和 # 思路：莫队算法，和小z的袜子差不多。不明白第一次tle#54是什么情况。把每一块的大小改成了常数之后就过了。 # 再交一遍就过了。。不过貌似根据最大数据把siz大小设置成一个常数比根号n要块很多==

2038: [2009国家集训队]小Z的袜子(hose) Time Limit: 20 Sec Memory Limit: 259 MB Submit: 5327 Solved: 2461 [Submit][Status][Discuss] Description

http://codeforces.com/contest/625/problem/D 题意：问能否找到一个s，满足s+s的反转=k 思路：如果是回文数。。。那么显然满足。除以2就可以得到答案。 代码实现 1 如果不是回文数。。那么考虑进位的情况。 2 要么从后一位进1，要么从前一位退10回来。 3 需要特殊考虑1开头的。 4 5 6 7/* *********************************************** 8Author :111qqz 9Created Time :2016年02月07日 星期日 18时28分39秒 10File Name :code/cf/#342/D.cpp 11************************************************ */ 12 13#include <cstdio> 14#include <cstring> 15#include <iostream> 16#include <algorithm> 17#include <vector> 18#include <queue> 19#include <set> 20#include <map> 21#include <string> 22#include <cmath> 23#include <cstdlib> 24#include <ctime> 25#include <sstream> 26#define fst first 27#define sec second 28#define lson l,m,rt<<1 29#define rson m+1,r,rt<<1|1 30#define ms(a,x) memset(a,x,sizeof(a)) 31typedef long long LL; 32#define pi pair < int ,int > 33#define MP make_pair 34 35using namespace std; 36const double eps = 1E-8; 37const int dx4[4]={1,0,0,-1}; 38const int dy4[4]={0,-1,1,0}; 39const int inf = 0x3f3f3f3f; 40const int N=1E5+7; 41bool vis[N]; 42 43void pre() 44{ 45 ms(vis,false); 46 for ( int i = 10 ; i <12000 ; i++) 47 { 48 int vala = i ; 49 stringstream ss; 50 ss<<vala; 51 string tmp = ss.str(); 52 53 reverse(tmp.begin(),tmp.end()); 54 55 int valb; 56 sscanf(tmp.c_str(),"%d",&valb); 57// cout<<i<<" "<<vala+valb<<endl; 58 if (vala+valb<N) vis[vala+valb] = true; 59 60 } 61 62 for ( int i = 1 ; i < N ; i++) 63 { 64 if (vis[i]) cout<<i<<endl; 65 } 66} 67char ans[N],s[N]; 68int n; 69int sum[N]; 70 71bool ok() 72{ 73 // cout<<"n:"<<n<<endl; 74 for ( int i = 0 ; i < n/2 ;) 75 { 76 int l = i ; 77 int r = n-1-i; 78 if (sum[l]==sum[r]) i++; 79 else if (sum[l]==sum[r]+1||sum[l]==sum[r]+11) 80 { 81 sum[l]--; 82 sum[l+1]+=10; 83 } 84 else if (sum[l]==sum[r]+10) 85 { 86 sum[r-1]--; 87 sum[r]+=10; 88 89 } 90 else return false; 91 } 92 93 if (n%2==1) 94 { 95 if (sum[n/2]%2==1) return false; 96 if (sum[n/2]>18||sum[n/2]<0) return false; 97 ans[n/2] = char(sum[n/2]/2 +'0'); 98// cout<<"ASDHJKASD"<<endl; 99 } 100 for ( int i = 0 ; i < n/2 ; i++) 101 { 102 if (sum[i]<0||sum[i]>18) return false; 103 ans[i] =(sum[i]+1)/2+'0'; 104 ans[n-1-i] =sum[i]/2+'0'; 105 } 106 return ans[0]>'0'; 107} 108int main() 109{ 110 #ifndef ONLINE_JUDGE 111 freopen("code/in.txt","r",stdin); 112 #endif 113 114 //pre(); 115 // 116 117 scanf("%s",s); 118 n = strlen(s); 119 for ( int i = 0 ; i < n ; i++) sum[i] = s[i] - '0'; 120 if (ok()) 121 { 122 cout<<ans<<endl; 123// cout<<"aaa"<<endl; 124 return 0; 125 } 126 127 if (s[0]=='1'&&n>1) 128 { 129 for ( int i = 0 ; i < n ; i++) 130 sum[i] = s[i+1]-'0'; 131 sum[0]+=10; 132 n--; 133 if (ok()) 134 { 135 cout<<ans<<endl; 136 return 0; 137 } 138 else 139 puts("0"); 140 } 141 else puts("0"); 142 143 144 #ifndef ONLINE_JUDGE 145 fclose(stdin); 146 #endif 147 return 0; 148}

http://codeforces.com/problemset/problem/621/E # 题意：有b组数，每组数均有n个且相同。你必须在每组选一个数，组成一个新数sum，使得sum % x == k，问方案数 % (1e9+7)。

http://codeforces.com/contest/621/problem/D # 题意：给出12个式子，问哪个最大。 思路：主要记住两个。一个是比较指数形式的数一个常用办法是取对数，同时要考虑是否能取对数，分情况讨论对于不能取对数的情况经过变换去取对数。第二个是取了两次对数后比较时候的最大值可能是小于0的。所以初始时置于0不够小。官方题解说得很清楚。