Posts

http://codeforces.com/problemset/problem/13/E 题意：给你n个洞，进入某个洞后会跑到另一个洞，到了另一个洞之后又可能会继续到下一个洞，问你从一个洞进去，钻了几个洞才会出来，在哪个洞出来 n 个整数a[i] 表示进入i这个洞之后会跑到 i+a[i]….

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). Solution of all of this problems are the same. You just need to know how to solve one of them. Example : You are asked some queries on an array _a_1, _a_2, …a, n. Each query give you numbers l and r and you should print a__l + a__l + 1 + … + a__r .

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个人可以少付一个人的钱，问最后两个教练每人要付多少钱。 思路：贪心。坑点在读题。。选手n个人，不要忘记两个教练，以及，钱数是两个教练平分。

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 需要注意的是：最大距离一定是从某点上取得，但是最小距离可能不在顶点上，而在某条边上。

写了几道莫队，总结下。 目前只会区间莫队。。树上莫队以后再补。 莫队算法学习 说说我自己的理解： 莫队算法是一类用来处理离线静态区间问题的算法。 必须是离线，而且对区间没有修改。 还要满足，如果我们知道区间[l,r]的答案，那么知道区间[l-1,r],[l+1,r],[l,r-1],[l,r+1]的答案都是平凡的。。也就是O(1)可以实现才可以。

https://ac.2333.moe/Problem/view.xhtml?id=1457 题意：求一段区间内数字个数的立方和。 思路：由于一共才1E5，而数字1E9，所以先离散化，再莫队，类似小z的袜子。 注意 ：%lld会WA，要用%I64d 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年02月17日 星期三 16时11分00秒 4File Name :code/nbut/1457.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=1E5+7; 34int a[N],b[N]; 35LL cnt[N]; 36int pos[N]; 37LL ans[N]; 38LL sum; 39int n,m; 40 41struct node 42{ 43 int l,r; 44 int id; 45 46 bool operator < (node b)const 47 { 48 if (pos[l]==pos[b.l]) return r<b.r; 49 return pos[l]<pos[b.l]; 50 } 51}q[N]; 52 53 54 55void update(int x,int d) 56{ 57 58 sum-=cnt[a[x]]*cnt[a[x]]*cnt[a[x]]; 59 cnt[a[x]]+=d; 60 sum +=cnt[a[x]]*cnt[a[x]]*cnt[a[x]]; 61 62} 63int main() 64{ 65 #ifndef ONLINE_JUDGE 66 freopen("code/in.txt","r",stdin); 67 #endif 68 69 while (scanf("%d",&n)!=EOF) 70 { 71 ms(cnt,0); 72 ms(ans,0); 73 sum = 0LL; 74 75 int siz = 330;//sqrt(100000); 76 for ( int i = 1 ; i <= n ; i++) 77 { 78 scanf("%d",&b[i]); 79 pos[i] = (i-1)/siz; 80 a[i] = b[i]; 81 } 82 83 sort(b+1,b+n+1); //离散化 84 int t = unique(b+1,b+n+1)-b-1; 85 for ( int i = 1 ; i <= n ; i++) a[i]=lower_bound(b+1,b+t+1,a[i])-b; 86 87 scanf("%d",&m); 88 for ( int i = 1 ; i <= m ; i++) 89 { 90 scanf("%d %d",&q[i].l,&q[i].r); 91 q[i].id = i ; 92 } 93 sort(q+1,q+m+1); 94 95 int pl=1,pr=0; 96 int id,l,r; 97 for ( int i = 1 ; i <= m ; i++) 98 { 99 id = q[i].id; 100 r = q[i].r; 101 l = q[i].l; 102 103 if (pr<r) 104 { 105 for ( int j = pr +1 ; j <= r ; j++) update(j,1); 106 } 107 else 108 { 109 for (int j = r+1 ; j <= pr ; j++) update(j,-1); 110 } 111 pr = r; 112 113 if (l<pl) 114 { 115 for ( int j = l ; j <= pl-1 ; j++) update(j,1); 116 } 117 else 118 { 119 for (int j = pl ; j <= l-1 ; j++) update(j,-1); 120 } 121 pl = l; 122 123 ans[id] = sum; 124 } 125 126 for ( int i = 1 ; i <= m ; i++) printf("%I64d\n",ans[i]); //用%lld会WA...也不给个警告 127 } 128 129 #ifndef ONLINE_JUDGE 130 fclose(stdin); 131 #endif 132 return 0; 133}

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 作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜子过程，于是他决定听天由命…… 具体来说，小Z把这N只袜子从1到N编号，然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双，甚至不在意两只袜子是否一左一右，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。 你的任务便是告诉小Z，他有多大的概率抽到两只颜色相同的袜子。当然，小Z希望这个概率尽量高，所以他可能会询问多个(L,R)以方便自己选择。

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)。 思路：数位dp.首先考虑b不是很大的一般情况。dp[i][j]表示处理到前i个块的时候结果为j的方案数。那么转移方程就是：**dp[i][(j_10+t)%x] = dp[i-1][j]_cnt[t] ** cnt[i]表示数字i出现的个数。