| 小象涂色 |
| 难度级别：C； 运行时间限制：1000ms； 运行空间限制：262144KB； 代码长度限制：2000000B |
|
试题描述
|
|
小象喜欢为箱子涂色。小象现在有c种颜色，编号为0~c-1；还有n个箱子，编号为1~n，最开始每个箱子的颜色为1。小象涂色时喜欢遵循灵感：它将箱子按编号排成一排，每次涂色时，它随机选择[L，R]这个区间里的一些箱子（不选看做选0个），为之涂上随机一种颜色。若一个颜色为a的箱子被涂上b色，那么这个箱子的颜色会变成（a*b）modc。请问在k次涂色后，所有箱子颜色的编号和期望为多少？ |
|
输入
|
|
第一行为T，表示有T组测试数据。
对于每组数据，第一行为三个整数n,c,k。 接下来k行，每行两个整数Li，Ri，表示第i个操作的L和R。 |
|
输出
|
|
对于每组测试数据，输出所有箱子颜色编号和的期望值，结果保留9位小数。
|
|
输入示例
|
|
3
3 2 2 2 2 1 3 1 3 1 1 1 5 2 2 3 4 2 4 |
|
输出示例
|
|
2.062500000
1.000000000 3.875000000 |
|
其他说明
|
|
数据范围：
40%的数据1 <= T <= 5，1 <= n, k <= 15，2 <= c <= 20 100%的数据满足1 <= T <= 10，1 <= n, k <= 50，2 <= c <= 100，1 <= Li <= Ri <= n |
首先，操作顺序是没有影响的，那么我们可以记录每个位置进行了多少次操作。
就可以写个DP，得出每个位置进行若干次操作后的期望颜色。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i;i=next[i]) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } double f[55][105]; int n,c,k,cnt[55]; int main() { dwn(T,read(),1) { n=read();c=read();k=read(); memset(f,0,sizeof(f)); memset(cnt,0,sizeof(cnt)); f[0][1]=1; rep(t,0,k-1) rep(j,0,c-1) { f[t+1][j]+=f[t][j]*0.5; rep(k,0,c-1) f[t+1][(j*k)%c]+=f[t][j]*(0.5/c); } double ans=0; rep(i,1,k) { int l=read(),r=read(); rep(j,l,r) cnt[j]++; } rep(i,1,n) rep(j,0,c-1) ans+=f[cnt[i]][j]*j; printf("%.9lf ",ans); } return 0; }
| 行动！行动！ |
| 难度级别：C； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
|
试题描述
|
|
大CX国的大兵Jack接到一项任务：敌方占领了n座城市（编号0~n-1），有些城市之间有双向道路相连。Jack需要空降在一个城市S，并徒步沿那些道路移动到T城市。虽然Jack每从一个城市到另一个城市都会受伤流血，但大CX国毕竟有着“过硬”的军事实力，它不仅已经算出Jack在每条道路上会损失的血量，还给Jack提供了k个“简易急救包”，一个包可以让Jack在一条路上的流血量为0。Jack想知道自己最少会流多少血，不过他毕竟是无脑的大兵，需要你的帮助。
|
|
输入
|
|
第一行有三个整数n,m,k，分别表示城市数，道路数和急救包个数。
第二行有两个整数，S,T。分别表示Jack空降到的城市编号和最终要到的城市。 接下来有m行，每行三个整数a,b,c，表示城市a与城市b之间有一条双向道路。 |
|
输出
|
|
Jack最少要流的血量。
|
|
输入示例
|
|
5 6 1
0 3 3 4 5 0 1 5 0 2 100 1 2 5 2 4 5 2 4 3 |
|
输出示例
|
|
8
|
|
其他说明
|
|
数据范围：
对于30%的数据,2<=n<=50,1<=m<=300,k=0; 对于50%的数据,2<=n<=600,1<=m<=6000,0<=k<=1; 对于100%的数据,2<=n<=10000,1<=m<=50000,0<=k<=10. |
拆点最短路。。。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i;i=next[i]) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } const int maxn=10010; const int maxm=200010; struct HeapNode { int u,d; bool operator < (const HeapNode& ths) const {return d>ths.d;} }; int n,m,k,s,t,first[maxn],next[maxm]; int to[maxm],dis[maxm],d[15][maxn],done[maxn*12]; priority_queue<HeapNode> Q; void spfa() { rep(i,0,k) rep(j,0,n-1) d[i][j]=1<<30; Q.push((HeapNode){s+n*k,0});d[k][s]=0; while(!Q.empty()) { if(done[Q.top().u]) {Q.pop();continue;} else done[Q.top().u]=1; int x=Q.top().u%n,k2=Q.top().u/n;Q.pop(); ren { if(d[k2][to[i]]>d[k2][x]+dis[i]) { d[k2][to[i]]=d[k2][x]+dis[i]; Q.push((HeapNode){to[i]+n*k2,d[k2][to[i]]}); } if(d[k2-1][to[i]]>d[k2][x]) { d[k2-1][to[i]]=d[k2][x]; Q.push((HeapNode){to[i]+n*k2-n,d[k2-1][to[i]]}); } } } } int main() { n=read();m=read();k=read(); s=read();t=read(); rep(i,1,m) { int x=read();to[i]=read();to[i+m]=x;dis[i+m]=dis[i]=read(); next[i]=first[x];first[x]=i;next[i+m]=first[to[i]];first[to[i]]=i+m; } spfa(); int ans=1<<30; rep(i,0,k) ans=min(ans,d[i][t]); printf("%d ",ans); return 0; }
| Hzwer的陨石 |
| 难度级别：C； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
|
试题描述
|
|
经过不懈的努力，Hzwer召唤了很多陨石。已知Hzwer的地图上共有n个区域，且一开始的时候第i个陨石掉在了第i个区域。有电力喷射背包的ndsf很自豪，他认为搬陨石很容易，所以他将一些区域的陨石全搬到了另外一些区域。 在ndsf愉快的搬运过程中，Hzwer想知道一些陨石的信息。对于Hzwer询问的每个陨石i，你必须告诉他，在当前这个时候，i号陨石在所在区域x、x区域共有的陨石数y、以及i号陨石被搬运的次数z。 |
|
输入
|
|
输入的第一行是一个正整数T。表示有多少组输入数据。
接下来共有T组数据，对于每组数据，第一行包含两个整数：N和Q。 接下来Q行，每行表示一次搬运或一次询问，格式如下： T A B：表示搬运，即将所有在A号球所在地区的陨石都搬到B号球所在地区去。 Q A：悟空想知道Ａ号陨石的x，y，z |
|
输出
|
|
对于第ｉ组数据，第一行输出“Case i：”接下来输出每一个询问操作的x，y，z，每一个询问操作的答案占一行。每组数据之间没有空行。
|
|
输入示例
|
|
2
3 3 T 1 2 T 3 2 Q 2 3 4 T 1 2 Q 1 T 1 3 Q 1 |
|
输出示例
|
|
Case 1:
2 3 0 Case 2: 2 2 1 3 3 2 |
|
其他说明
|
|
数据范围：
20%的数据保证：0≤T≤20，2＜N＜＝100，2＜Q＜＝100。 100%的数据保证：0≤T≤100，2＜N＜＝10000，2＜Q＜＝10000。 对于所有数据保证搬运操作中AB在Ｎ的范围内且所在区域不相同。： |
前两问很好做，写个并查集就行了。第三问可以这么做：如果x区域的陨石全部搬到y区域，那么将x->y的值+1，则x地区的陨石被搬运的次数就是x到根节点的距离，并查集记录一下信息就行了。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } const int maxn=10010; int pa[maxn],s[maxn],d[maxn]; int findset(int x) { if(pa[x]==x) return x; int res=findset(pa[x]);d[x]+=d[pa[x]]; return pa[x]=res; } int main() { int T=read(); rep(Case,1,T) { printf("Case %d: ",Case); int n=read(),m=read(); rep(i,1,n) pa[i]=i,s[i]=1,d[i]=0; rep(i,1,m) { char cmd[12];scanf("%s",cmd); if(cmd[0]=='Q') { int y,x=findset(y=read()); printf("%d %d %d ",x,s[x],d[y]); } else { int x=findset(read()),y=findset(read()); pa[x]=y;s[y]+=s[x];d[x]++; } } } return 0; }
| 挖掘机 |
| 难度级别：C； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
|
试题描述
|
|
今天，丧尸czy开着挖掘机去上学(……)。但是他发现他的mz满天下，所以一路上他碰到了好多他的mz。一开始他以1km/min的速度(=60km/h……)开着挖掘机前进。他发现他只会在恰好到达某一时刻或者到达某个距离遇到mz。每次遇到mz，czy都会毫不犹豫的把她们顺路捎走(^_^)。但是他实在是太虚了，以至于当有i个mz时他的速度下降到1/(i+1)。具体说，一开始czy以1km/min速度前进，有1个mz的时候速度变为1/2 km/min，有2个时变为1/3 km/min……以此类推。现在问题来了，给出每个mz在何时出现，请你算出czy到学校要多久。
|
|
输入
|
|
输入第一行2个数n，m，分别表示mz数和czy与学校的距离(km)
接下来2到n+1行由字符串与数字构成 Dist x表示在距离达到x km时出现一个mz Time x表示在时间达到x min时出现一个mz |
|
输出
|
|
输出一个整数，表示到达学校的时间。如果不能整除，直接输出整数部分即可。
|
|
输入示例
|
|
2 20
Time 3 Dist 10 |
|
输出示例
|
|
47
|
|
其他说明
|
|
数据范围
对于30%数据，n,m<=50 对于50%数据，n,m<=2000 对于100%数据，n,m<=200000,x<=10^9,保证输入的数字都是整数 |
奇怪的题目，排序乱搞。。。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } typedef long long ll; const int maxn=200010; int A[maxn],B[maxn],n1,n2; char s[20]; int main() { int n=read(),m=read(); rep(i,1,n) { scanf("%s",s); if(s[0]=='T') A[++n1]=read(); else B[++n2]=read(); } B[++n2]=m; sort(A+1,A+n1+1);sort(B+1,B+n2+1); double ans=0,p=0.0;int c=1,cur=1; rep(i,1,n2) { while(cur<=n1&&ans+c*(B[i]-p)>A[cur]) { p+=(A[cur]-ans)/c;ans=A[cur];c++;cur++; } ans+=c*(B[i]-p);p=B[i];c++; } printf("%lld ",(ll)ans); return 0; }
| 藏宝图 |
| 难度级别：C； 运行时间限制：4000ms； 运行空间限制：262144KB； 代码长度限制：2000000B |
|
试题描述
|
|
Czy发现了一张奇怪的藏宝图。图上有n个点，m条无向边。已经标出了图中两两之间距离dist。但是czy知道，只有当图刚好又是一颗树的时候，这张藏宝图才是真的。如果藏宝图是真的，那么经过点x的边的边权平均数最大的那个x是藏着宝物的地方。请计算这是不是真的藏宝图，如果是真的藏宝之处在哪里。
|
|
输入
|
|
输入数据第一行一个数T,表示T组数据。
对于每组数据，第一行一个n，表示藏宝图上的点的个数。 接下来n行,每行n个数，表示两两节点之间的距离。 |
|
输出
|
|
输出一行或两行。第一行”Yes”或”No”，表示这是不是真的藏宝图。
若是真的藏宝图，第二行再输出一个数，表示哪个点是藏宝之处。 |
|
输入示例
|
|
2
3 0 7 9 7 0 2 9 2 0 3 0 2 7 2 0 9 7 9 0 |
|
输出示例
|
|
Yes
1 Yes 3 样例解释:第一棵树的形状是1--2--3。1、2之间的边权是7，2、3之间是2。 第二棵树的形状是2--1--3。2、1之间的边权是2，1、3之间是7。 |
|
其他说明
|
|
数据范围
对于30%数据，n<=50,1<=树上的边的长度<=10^9。 对于50%数据，n<=600. 对于100%数据，1<=n<=2500 0<=dist[i][j]<=10^12,T<=5 |
如果一个图是树，则整个图的最小生成树为这个图。
可以计算出原图的最小生成树，重建整个图，再重判是否有矛盾即可。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i;i=next[i]) using namespace std; typedef long long ll; inline ll read() { ll x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } const int maxn=2510; struct Edge { int u,v;ll w; bool operator < (const Edge& ths) const {return w<ths.w;} }E[maxn*maxn/2]; ll d[maxn][maxn]; int n,pa[maxn],first[maxn],next[maxn<<1],to[maxn<<1],dis[maxn<<1],e; int findset(int x) {return x==pa[x]?x:pa[x]=findset(pa[x]);} void AddEdge(int u,int v,int w) { to[++e]=v;dis[e]=w;next[e]=first[u];first[u]=e; to[++e]=u;dis[e]=w;next[e]=first[v];first[v]=e; } int vis[maxn]; ll dist[maxn]; queue<int> Q; void bfs(int x) { memset(vis,0,sizeof(vis)); Q.push(x);vis[x]=1;dist[x]=0; while(!Q.empty()) { x=Q.front();Q.pop(); ren if(!vis[to[i]]) { vis[to[i]]=1; dist[to[i]]=dist[x]+dis[i]; Q.push(to[i]); } } } int main() { dwn(T,read(),1) { n=read();int m=0;e=0;memset(first,0,sizeof(first)); rep(i,1,n) rep(j,1,n) d[i][j]=read(); rep(i,1,n) { pa[i]=i;int best=0; rep(j,1,n) if(i<j) E[++m]=(Edge){i,j,d[i][j]}; } sort(E+1,E+m+1); rep(i,1,m) { int x=findset(E[i].u),y=findset(E[i].v); if(x!=y) pa[x]=y,AddEdge(E[i].u,E[i].v,E[i].w); } int ok=1; rep(i,1,n) { bfs(i); rep(j,1,n) if(d[i][j]!=dist[j]) ok=0; } if(!ok) puts("No"); else { puts("Yes"); if(n==1) puts("1"); else { int ans=0;double mx=0.0; rep(x,1,n) { int cnt=0;double val=0; ren cnt++,val+=dis[i]; val/=cnt;if(val>mx) mx=val,ans=x; } printf("%d ",ans); } } } return 0; }
| 最大公约数 |
| 难度级别：C； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
|
试题描述
|
|
话说CD比较欠扁，他表示在课室的日子没有教主在旁边打他的日子太寂寞了，所以这一晚，他终于来到了电脑室被打。由于CD是大家的宠物，于是大家都来打CD了。电脑室里有n个人，第i个人希望打CD ai下。但是太多人打CD，他又会不爽，于是他规定只能有K个人打到他，并且为了公平起见，最终K个人打他的次数都必须是相同的，CD规定这个次数就是这K个人希望打他的次数的最大公约数。为什么是最大公约数呢？因为他觉得被打的次数是GCD的话他才会变成Glad CD。之前说了，CD比较欠扁，于是CD希望，K个人打他的次数的和最大。你能告诉他他最后总共会被打多少下么？ |
|
输入
|
|
第一行两个正整数n，k。
第二行n个正整数，表示每个人希望打CD多少下。 |
|
输出
|
|
输出一个正整数表示CD会被打多少下
|
|
输入示例
|
|
3 1
1 2 3 |
|
输出示例
|
|
3
|
|
其他说明
|
|
数据说明
对于30%的数据，保证k≤n≤20。 对于50%的数据，保证输入中所有数小于5000。 对于100%的数据，保证输入中所有数小于500000，k≤n。 |
枚举答案ans，数一数有多少数是ans的倍数。根据调和数列定理，时间复杂度为O(nlogn)
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } const int maxn=500010; int S[maxn],ans; int main() { int n=read(),k=read(); rep(i,1,n) S[read()]++; rep(i,1,500000) { int cnt=0; for(int j=i;j<=500000;j+=i) cnt+=S[j]; if(cnt>=k) ans=max(ans,i); } printf("%lld ",(long long)ans*k); return 0; }
| 密码 |
| 难度级别：C； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
|
试题描述
|
|
哪里有压迫，哪里就有反抗。 moreD的宠物在法庭的帮助下终于反抗了。作为一只聪明的宠物，他打算把魔法使moreD的魔法书盗去，夺取moreD的魔法能力。但moreD怎么会让自己的魔法书轻易地被盗取？moreD在魔法书上设置了一个密码锁，密码锁上有一个问题。 施以斯卧铺魔法吧，你有M次机会，如此将得完美密码。 然后是一串小写字母串。 moreD的宠物斯卧铺魔法就是施法时的字符串其中相邻两位交换。 而moreD对于完美密码的定义自然是最小字典序了。 请帮助moreD的宠物，想出密码吧。 |
|
输入
|
|
第一行一个整数M，表示操作次数。
第二行一串小写字母组成的字符串S，如题目所示。 |
|
输出
|
|
输出完美密码
|
|
输入示例
|
|
3
dcba |
|
输出示例
|
|
adcb
|
|
其他说明
|
|
【数据范围】
对于30%的数据|S|≤10 对于60%的数据|S|≤3,000 对于100%的数据8≤|S|≤100,000 M≤(|S|-8)^2+2 【后记】 宠物最终战胜了moreD,和自己的宠物快乐地生活着。 【样例解释】 先对第3，4两位施法，字符串变成dcab，然后对第2，3两位施法，字符串变成dacb，最后对第1，2两位施法，字符串变成adcb。 |
按位贪心，考虑将字符c换到该位置是否可行。注意每次移动[l,r]区间的同时会让[l,r]中的所有字符向左移一位，可以用个数据结构来维护单点修改区间和。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; typedef long long ll; const int maxn=100010; char s[maxn]; int n,c[maxn],first[maxn],next[maxn]; ll m; void add(int x,int v) { for(;x<=n;x+=x&-x) c[x]+=v; } int sum(int x) { int res=0; for(;x;x-=x&-x) res+=c[x]; return res; } int main() { scanf("%lld%s",&m,s+1);n=strlen(s+1); dwn(i,n,1) next[i]=first[s[i]-'a'],first[s[i]-'a']=i,add(i,1); rep(i,1,n) { int j=0,tmp; for(;j<=25;j++) if(first[j]&&(tmp=sum(first[j]-1))<=m) { m-=tmp;add(first[j],-1);first[j]=next[first[j]];break; } putchar(j+'a'); } return 0; }
| 取数 |
| 难度级别：C； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
|
试题描述
|
|
有一个取数的游戏。初始时，给出一个环，环上的每条边上都有一个非负整数。这些整数中至少有一个0。然后，将一枚硬币放在环上的一个节点上。两个玩家就是以这个放硬币的节点为起点开始这个游戏，两人轮流取数，取数的规则如下： （1）选择硬币左边或者右边的一条边，并且边上的数非0； （2）将这条边上的数减至任意一个非负整数(至少要有所减小)； （3）将硬币移至边的另一端。 如果轮到一个玩家走，这时硬币左右两边的边上的数值都是0，那么这个玩家就输了。 如下图，描述的是Alice和Bob两人的对弈过程，其中黑色节点表示硬币所在节点。结果图(d)中，轮到Bob走时，硬币两边的边上都是0，所以Alcie获胜。
现在，你的任务就是根据给出的环、边上的数值以及起点（硬币所在位置），判断先走方是否有必胜的策略。 |
|
输入
|
|
第一行一个整数N（N≤20），表示环上的节点数。
第二行N个数，数值不超过30，依次表示N条边上的数值。硬币的起始位置在第一条边与最后一条边之间的节点上。 |
|
输出
|
|
仅一行。若存在必胜策略，则输出“YES”，否则输出“NO”。
|
|
输入示例
|
|
样例输入1
4 2 5 3 0 样例输入2 3 0 0 0 |
|
输出示例
|
|
样例输入1
YES 样例输入2 NO |
。。。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } int A[25],n; int main() { n=read(); rep(i,1,n) A[i]=read(); int r=n,l=0; while(A[r]) r--; while(A[l+1]) l++; r=n-r; if(l&1||r&1) puts("YES"); else puts("NO"); return 0; }
| 游戏 |
| 难度级别：C； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
|
试题描述
|
|
windy学会了一种游戏。 如： 1 2 3 4 5 6 2 3 1 5 4 6 3 1 2 4 5 6 1 2 3 5 4 6 2 3 1 4 5 6 3 1 2 5 4 6 1 2 3 4 5 6 这时，我们就有若干排1到N的排列，上例中有7排。 现在windy想知道，对于所有可能的对应关系，有多少种可能的排数。 |
|
输入
|
|
输入文件game.in包含一个整数，N。
|
|
输出
|
|
输出文件game.out包含一个整数，可能的排数。
|
|
输入示例
|
|
【输入样例一】
3 【输入样例二】 10 |
|
输出示例
|
|
【输出样例一】
3 【输出样例二】 16 |
|
其他说明
|
|
数据规模和约定
30%的数据，满足 1 <= N <= 10 。 100%的数据，满足 1 <= N <= 1000 。 |
将每个置换分解成循环的形式，则操作数为循环长度的LCM。
那么问题转化成将N拆成若干正整数的和，问LCM有几种。
考虑唯一分解定理，打出1到N素数表，设f[i][j]表示用了前i个素数目前和为j的可能数，转移就很简单了。
最后答案=∑f[cnt][i]|1<=i<=N。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } typedef long long ll; const int maxn=1010; int vis[maxn],p[maxn],n,cnt; ll ans,f[170][maxn]; void init() { rep(i,2,n) if(!vis[i]) { p[++cnt]=i; for(int j=i*i;j<=n;j+=i) vis[j]=1; } } int main() { n=read();init(); f[0][0]=1; rep(i,1,cnt) { rep(j,0,n) f[i][j]=f[i-1][j]; for(int j=p[i];j<=n;j*=p[i]) rep(k,0,n-j) f[i][j+k]+=f[i-1][k]; } rep(i,0,n) ans+=f[cnt][i]; printf("%lld ",ans); return 0; }
| 迎接仪式 |
| 难度级别：C； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
|
试题描述
|
|
LHX教主要来X市指导OI学习工作了。为了迎接教主，在一条道路旁，一群Orz教主er穿着文化衫站在道路两旁迎接教主，每件文化衫上都印着大字。一旁的Orzer依次摆出“欢迎欢迎欢迎欢迎……”的大字，但是领队突然发现，另一旁穿着“教”和“主”字文化衫的Orzer却不太和谐。 为了简单描述这个不和谐的队列，我们用“j”替代“教”，“z”替代“主”。而一个“j”与“z”组成的序列则可以描述当前的队列。为了让教主看得尽量舒服，你必须调整队列，使得“jz”子串尽量多。每次调整你可以交换任意位置上的两个人，也就是序列中任意位置上的两个字母。而因为教主马上就来了，时间仅够最多作K次调整（当然可以调整不满K次），所以这个问题交给了你。 |
|
输入
|
|
输入文件welcome.in的第1行包含2个正整数N与K，表示了序列长度与最多交换次数。
第2行包含了一个长度为N的字符串，字符串仅由字母“j”与字母“z”组成，描述了这个序列。 |
|
输出
|
|
输出文件welcome.out仅包括一个非负整数，为调整最多K次后最后最多能出现多少个“jz”子串。
|
|
输入示例
|
|
5 2
zzzjj |
|
输出示例
|
|
2
|
|
其他说明
|
|
【样例说明】
第1次交换位置1上的z和位置4上的j，变为jzzzj； 第2次交换位置4上的z和位置5上的j，变为jzzjz。 最后的串有2个“jz”子串。 【数据规模】 对于10%的数据，有N≤10； 对于30%的数据，有K≤10； 对于40%的数据，有N≤50； 对于100%的数据，有N≤500，K≤100 |
这道题想法很巧妙。将交换操作认为是两步操作：1、将j变成z。2、将z变成j。
设f[i][j][k]表示[1,i]，进行了j次操作1，k次操作2最多的jz数。
1.f[i][j][k]=f[i-1][j][k];
2.f[i][j][k]=f[i-2][j-(A[i-1]=='j')][k-(A[i]=='z')]+1
只有当操作1和操作2数量相同时才认为是合法操作。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } const int maxn=510; const int maxk=110; char s[maxn]; int f[maxn][maxk][maxk],ans; int main() { int n=read(),m=read();scanf("%s",s+1); rep(i,2,n) rep(x,0,m) rep(y,0,m) { f[i][x][y]=f[i-1][x][y]; int t1=s[i-1]=='z',t2=s[i]=='j'; if(x>=t1&&y>=t2) f[i][x][y]=max(f[i][x][y],f[i-2][x-t1][y-t2]+1); if(x==y) ans=max(ans,f[i][x][y]); } int cnt1=0,cnt2=0; rep(i,1,n) cnt1+=s[i]=='j',cnt2+=s[i]=='z'; printf("%d ",min(ans,min(cnt1,cnt2))); return 0; }
| 连连看 |
| 难度级别：C； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
|
试题描述
|
|
有时大型游戏玩腻味了，小Z也会玩玩弱智级的小游戏，比如连连看。但小Z眼力不行，常常得分很低。于是，他找到了你，希望你能帮他找出一种获胜方案。 连连看的游戏规则很简单：玩家可以将 2 个相同图案的牌连接起来，连接线不多于 3 条线段，就可以成功将两个牌消除。将游戏界面上的牌全部消除掉，玩家就胜利了。 |
|
输入
|
|
输入文件card.in的第一行为两个正整数m和n，表示连连看游戏的矩阵大小。
接下来的m行，每行n个英文大写字母（为了计算方便，只用A~E五个字母），表示牌的种类，相同字母表示同种牌。 |
|
输出
|
|
输出文件card.out。
若能获胜，则输出共一行，包括m×n/2个英文大写字母，第i个字母表示第i次消除的牌的种类。若有多解，输出字典顺序最小的解。 若不能获胜，则输出共一行，包括字符串“Game over.”。 |
|
输入示例
|
|
输入样例1
2 1 A A 输入样例2 2 1 A B |
|
输出示例
|
|
输出样例1
A 输出样例2 Game over. |
|
其他说明
|
|
限制：
100%的数据满足：m×n<=12 |
超级无敌大暴力。。。
调了2h+。。。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<iostream> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } char Map[13][13]; const int mx[]={1,-1,0,0}; const int my[]={0,0,-1,1}; int n,m,vis[13][13][5][4]; string ans; int dfs2(int x,int y,int x1,int y1,int dir,int t) { if(vis[x][y][dir][t]) return 0;vis[x][y][dir][t]=1; if(t>2) return 0; if(x==x1&&y==y1) return 1; int nx=x+mx[dir],ny=y+my[dir]; if(nx>=0&&ny>=0&&nx<=n+1&&ny<=m+1&&!Map[nx][ny]) if(dfs2(nx,ny,x1,y1,dir,t)) return 1; rep(ndir,0,3) if(dfs2(x,y,x1,y1,ndir,t+1)) return 1; return 0; } int check(int x1,int y1,int x2,int y2) { rep(dir,0,3) { memset(vis,0,sizeof(vis)); if(dfs2(x1,y1,x2,y2,dir,0)) return 1; } return 0; } void dfs(int cur,int final,string cd) { if(cur==final) ans=min(ans,cd); else { rep(x,1,n) rep(y,1,m) rep(nx,1,n) rep(ny,1,m) if(Map[x][y]&&Map[nx][ny]&&Map[x][y]==Map[nx][ny]) { if(x==nx&&ny==y) continue; char c=Map[nx][ny];Map[nx][ny]=Map[x][y]=0; if(check(x,y,nx,ny)) dfs(cur+1,final,cd+c); Map[nx][ny]=Map[x][y]=c; } } } int main() { n=read();m=read(); if(n*m&1) puts("Game over."); else { rep(i,1,n) scanf("%s",Map[i]+1); rep(j,0,m+1) Map[0][j]=Map[n+1][j]=0; rep(j,0,n+1) Map[j][0]=Map[j][m+1]=0; ans="ZZZZZZZ";dfs(0,n*m/2,""); if(ans=="ZZZZZZZ") puts("Game over."); else cout<<ans<<endl; } return 0; }
| LazyChild黑OJ |
| 难度级别：C； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
|
试题描述
|
|
LazyChild开了一家“善良OJ”。但大多数人都不知道，这其实是家黑OJ。亲爱的同学，请不要惊讶，古时候有黑店，现代为什么不能有黑OJ呢？每AC一道题，网站便会自动在电脑上安装一种木马。LazyChild通过窃取信息获取收益（如网游帐号、OI资料、YuanY和TT的照片等等）。 作为一名资深黑客，老Z某日突然发现，“善良OJ”上的木马，自己电脑上都没有。这可十分让他过意不去。老Z决定通过多A题，来丰富自己电脑的病毒库。 经过调查，老Z发现，很多木马是不能共存的。比如“和谐”木马与“团结”木马，两者只能任选其一。然而，老Z是个完美主义者，他想要自己的病毒库尽可能充实。 老Z不懈的追求最终感动了上天。天上的神仙（半仙？）“牛人雨”给这个问题稍稍降低了一点难度。神仙规定，对于n种木马，有且仅有(n-1)对不能共存，并且对于每种木马，都存在至少一个木马与之不能共存。 老Z不在乎自己AC多少题。请告诉他，他最多能从“善良OJ”上获取木马的个数。 |
|
输入
|
|
第一行，一个正整数n，表示木马个数。
剩余(n-1)行，每行一对木马，表示他们不能共存。（保证相同的木马可以共存，任意不同两行的描述不等价） 木马编号从0至(n-1) |
|
输出
|
|
一行，老Z最多获得木马的个数。你可以认为开始时没有任何木马。
|
|
输入示例
|
|
3
0 1 1 2 |
|
输出示例
|
|
2
|
|
其他说明
|
|
【数据规模】
对于100％的数据，1<=n<=200 |
树上独立集。写个树上DP或匹配算法都行。。。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i;i=next[i]) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } const int maxn=210; int first[maxn],next[maxn<<1],to[maxn<<1],e; void AddEdge(int u,int v) { to[++e]=v;next[e]=first[u];first[u]=e; to[++e]=u;next[e]=first[v];first[v]=e; } int f[maxn][2]; int dp(int x,int tp,int fa) { int& ans=f[x][tp]; if(ans>=0) return ans; ans=0; if(!tp) { int v1=0,v2=0; ren if(to[i]!=fa) { v1+=dp(to[i],0,x); v2+=dp(to[i],1,x); } ans=max(v1,v2+1); } else ren if(to[i]!=fa) ans+=dp(to[i],0,x); return ans; } int main() { memset(f,-1,sizeof(f)); int n=read(); rep(i,2,n) AddEdge(read()+1,read()+1); printf("%d ",dp(1,0,-1)); return 0; }
| 机房人民大团结 |
| 难度级别：C； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
|
试题描述
|
|
最近，机房出了一个不团结分子：Dr.Weissman。他经常欺骗同学们吃一种“教授糖豆”，使同学们神志不清，殴打他人，砸烂计算机，破坏机房团结。幸运地，一个和谐家认清了Dr.Weissman的本质。机房人民团结在一起，共同对抗Dr.Weissman及“教授糖豆”。 同学们十分具有社会责任感：他们害怕“教授糖豆”流向社会，导致动乱。于是，刚才提到的和谐家身先士卒，为了实验，品尝“教授糖豆”。 每个“教授糖豆”的性质都有所不同。同志们已经研究出每个糖豆对人的影响。具体地，每个糖豆都有一个破坏值，吃掉这颗糖豆后，身先士卒的和谐家会对机房造成一定的破坏，破坏程度为先前累积的破坏值加上本次食用糖豆的破坏值，而且这颗“教授糖豆”的破坏值会加入累积。为了减小实验造成的破坏，同学们准备了几颗“治疗糖豆“，功能是无条件将累积的“破坏值”清零。 由于实验要求，和谐家只能按照给定的顺序吃掉“教授糖豆”，但可以随时吃掉一颗或多颗“治疗糖豆”。 你能帮助和谐家同志尽量减小实验所造成的破坏吗？ |
|
输入
|
|
第一行，两个数，用空格，分隔开，一个n，一个m。（n，m均为正整数。）n表示“教授糖豆”的数目，m表示“治疗糖豆”的数目。
剩余n行，每行1个正整数，表示“教授糖豆”的破坏值。和谐家必须按照给定的顺序，一次一个，吃掉所有“教授糖豆”。 |
|
输出
|
|
一行，一个数，表示实验造成的最小破坏。
|
|
输入示例
|
|
3 1
1 2 3 |
|
输出示例
|
|
7
|
|
其他说明
|
|
【数据规模】
对于100%的数据，1<=n<=100，m<=n 所有破坏值的加和小于10^9。 |
设f[i][j]表示已经吃了前i个“教授糖豆”，已用了j个“治疗糖豆”的最小破坏。
随便优化优化就行了。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } typedef long long ll; const int maxn=110; int n,m,A[maxn]; ll f[maxn][maxn],g[maxn][maxn]; int main() { n=read();m=read()+1; rep(i,1,n) A[i]=read(); rep(l,1,n) { ll val=0; rep(r,l,n) val+=A[r],g[l][r]=g[l][r-1]+val; } rep(i,1,n) f[0][i]=1ll<<60; rep(i,1,n) { f[i][1]=g[1][i]; rep(j,2,i) { f[i][j]=1ll<<60; rep(k,j-1,i-1) f[i][j]=min(f[i][j],f[k][j-1]+g[k+1][i]); } rep(j,i+1,n) f[i][j]=1ll<<60; } printf("%lld ",f[n][m]); return 0; }
| 四轮车 |
| 难度级别：A； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
|
试题描述
|
|
在地图上散落着n个车轮，小J想用它们造一辆车。要求如下： 1. 一辆车需要四个车轮，且四个车轮构成一个正方形 2.车轮不能移动 你需要计算有多少种造车的方案（两个方案不同当且仅当所用车轮不全相同，坐标相同的两个车轮视为不同车轮）。 |
|
输入
|
|
第一行一个整数n
接下来n行，每行两个整数x y，表示在(x,y)处有一个车轮 |
|
输出
|
|
一行一个整数，表示方案数
|
|
输入示例
|
|
9
0 0 1 0 2 0 0 2 1 2 2 2 0 1 1 1 2 1 |
|
输出示例
|
|
6
|
|
其他说明
|
|
【数据范围】
30%的数据保证n≤30 100%的数据保证1≤n≤1000;|x|,|y|<20000 |
这道题BJWC出过，不过范围是1<=N<=50000。
至于1<=N<=1000，直接枚举两角用个hash判其余两点就行了。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[p];i;i=next[i]) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } const int maxn=1010; const int HASH=937; struct Hash_Map { int x[maxn],y[maxn],cnt[maxn],next[maxn],n; int first[HASH]; void init() { memset(first,0,sizeof(first)); memset(cnt,0,sizeof(cnt)); n=0; } void insert(int X,int Y) { int p=(X*Y)%HASH;if(p<0) p+=HASH; ren if(x[i]==X&&y[i]==Y) {cnt[i]++;return;} x[++n]=X;y[n]=Y;cnt[n]=1;next[n]=first[p];first[p]=n; } int query(int X,int Y) { int p=(X*Y)%HASH;if(p<0) p+=HASH; ren if(x[i]==X&&y[i]==Y) return cnt[i]; return 0; } }S; int n,x[maxn],y[maxn]; int solve() { S.init();int res=0; rep(i,1,n) S.insert(x[i],y[i]); rep(i,1,n) rep(j,i+1,n) if(x[i]==x[j]) { int gap=abs(y[i]-y[j]); res+=S.query(x[i]-gap,y[i])*S.query(x[i]-gap,y[j]); } return res; } int main() { n=read(); rep(i,1,n) x[i]=read(),y[i]=read(); int ans=solve(); rep(i,1,n) { int a=x[i],b=y[i]; x[i]=a+b;y[i]=a-b; } printf("%d ",ans+solve()); return 0; }
| 盘子序列 |
| 难度级别：A； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
|
试题描述
|
|
有n个盘子。盘子被生产出来后，被按照某种顺序摞在一起。初始盘堆中如果一个盘子比所有它上面的盘子都大，那么它是安全的，否则它是危险的。称初始盘堆为A，另外有一个开始为空的盘堆B。为了掩盖失误，生产商会对盘子序列做一些“处理”，每次进行以下操作中的一个：(1)将A最上面的盘子放到B最上面；(2)将B最上面的盘子给你。在得到所有n个盘子之后，你需要判断初始盘堆里是否有危险的盘子。 |
|
输入
|
|
输入文件包含多组数据（不超过10组）
每组数据的第一行为一个整数n 接下来n个整数，第i个整数表示你收到的第i个盘子的大小 |
|
输出
|
|
对于每组数据，如果存在危险的盘子，输出”J”，否则输出”Y”
|
|
输入示例
|
|
3
2 1 3 3 3 1 2 |
|
输出示例
|
|
Y
J |
|
其他说明
|
|
【数据范围】
20%的数据保证n<=8 80%的数据保证n<=1,000 100%的数据保证1<=n<=100,000，0<盘子大小<1,000,000,000且互不相等 |
离散后用个stack判判就行了。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } const int maxn=100010; int n,top,A[maxn],T[maxn],S[maxn]; int main() { while(scanf("%d",&n)==1) { rep(i,1,n) T[i]=A[i]=read(); sort(T+1,T+n+1); rep(i,1,n) A[i]=lower_bound(T+1,T+n+1,A[i])-T; int cur=1;top=0; rep(i,1,n) { S[++top]=i; while(top&&S[top]==A[cur]&&cur<=n) top--,cur++; } puts(top?"J":"Y"); } return 0; }
| 点名 |
| 难度级别：A； 运行时间限制：3000ms； 运行空间限制：262144KB； 代码长度限制：2000000B |
|
试题描述
|
|
在J班的体育课上，同学们常常会迟到几分钟，但体育老师的点名却一直很准时。老师只关心同学的身高，他会依次询问当前最矮的身高，次矮的身高，第三矮的身高，等等。在询问的过程中，会不时地有人插进队伍里。你需要回答老师每次的询问。 |
|
输入
|
|
第一行两个整数n m，表示先后有n个人进队，老师询问了m次
第二行n个整数，第i个数Ai表示第i个进入队伍的同学的身高为Ai 第三行m个整数，第j个数Bj表示老师在第Bj个同学进入队伍后有一次询问 |
|
输出
|
|
m行，每行一个整数，依次表示老师每次询问的答案。数据保证合法
|
|
输入示例
|
|
7 4
9 7 2 8 14 1 8 1 2 6 6 |
|
输出示例
|
|
9
9 7 8 |
|
其他说明
|
|
【样例解释】
(9){No.1 = 9}; (9 7){No.2 = 9}; (9 7 2 8 14 1){No.3 = 7; No.4 = 8} 【数据范围】 40%的数据保证n≤1000 100%的数据保证1≤m≤n≤30000;0≤Ai<2^32 |
Treap练习。。。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; typedef long long ll; inline ll read() { ll x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } const int maxn=60010; struct Node { Node* ch[2]; int r,s; ll v; void maintain() {s=ch[0]->s+ch[1]->s+1;} }nodes[maxn],*null=&nodes[0]; int ToT; Node* newnode(ll v) { Node* o=&nodes[++ToT]; o->v=v;o->ch[0]=o->ch[1]=null;o->s=1;o->r=rand(); return o; } void rotate(Node* &o,int d) { Node* k=o->ch[d^1];o->ch[d^1]=k->ch[d];k->ch[d]=o; o->maintain();k->maintain();o=k; } void insert(Node* &o,ll v) { if(o==null) o=newnode(v); else { int d=v>o->v;insert(o->ch[d],v); if(o->ch[d]->r>o->r) rotate(o,d^1); else o->maintain(); } } ll query(Node* &o,ll k) { if(k>o->s) return -1; if(o->ch[0]->s+1==k) return o->v; if(o->ch[0]->s>=k) return query(o->ch[0],k); return query(o->ch[1],k-o->ch[0]->s-1); } void print(Node* &o) { if(o==null) return; print(o->ch[0]); printf("%d ",o->v); print(o->ch[1]); } Node *root=null; struct Operation { int type,time,id; ll v; bool operator < (const Operation& ths) const { if(time!=ths.time) return time<ths.time; return type<ths.type; } }Q[maxn]; ll n,m,ans[maxn]; int main() { n=read();m=read(); rep(i,1,n) Q[i]=(Operation){0,i,0,read()}; rep(i,1,m) Q[i+n]=(Operation){1,read(),i,i}; n+=m;sort(Q+1,Q+n+1); rep(i,1,n) { if(!Q[i].type) insert(root,Q[i].v); else ans[Q[i].id]=query(root,Q[i].v); } rep(i,1,m) printf("%lld ",ans[i]); return 0; }
| 序列问题 |
| 难度级别：A； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
|
试题描述
|
|
小H 是个善于思考的学生，她正在思考一个有关序列的问题。 她的面前浮现出了一个长度为n 的序列{ai}，她想找出两个非空的集合S、T。 这两个集合要满足以下的条件： 1. 两个集合中的元素都为整数，且都在[1, n] 里，即Si，Ti ∈[1, n]。 2. 对于集合S 中任意一个元素x，集合T 中任意一个元素y，满足x < y。 3. 对于大小分别为p, q 的集合S 与T，满足 a[s1] xor a[s2] xor a[s3] ... xor a[sp] = a[t1] and a[t2]and a[t3] ... and a[tq]. 小H 想知道一共有多少对这样的集合(S,T)，你能帮助她吗？ |
|
输入
|
|
第一行，一个整数n
第二行，n 个整数，代表ai。 |
|
输出
|
|
仅一行，表示最后的答案，保证答案在long long范围内。
|
|
输入示例
|
|
4
1 2 3 3 |
|
输出示例
|
|
4
|
|
其他说明
|
|
【样例解释】
S = {1,2}, T = {3}， 1 ^ 2 = 3 = 3 (^为异或) S = {1,2}, T = {4}, 1 ^ 2 = 3 = 3 S = {1,2}， T = {3，4} 1 ^ 2 = 3 & 3 = 3 （&为与运算） S = {3}， T = {4} 3 = 3 = 3 【数据范围】 30%: 1 <= n <= 10 60%: 1 <= n <= 100 100%: 1 <= n <= 1000, 0 <= ai < 1024 |
因为对于集合S 中任意一个元素x，集合T 中任意一个元素y，满足x < y。
所以问题其实是将序列分为前后两半，且前一半选出一些数的异或值=后一半选出一些数的且值。
以前一半的异或值为例：
设f[i][j][0]表示前i个数，异或和为j，且选了最后一个数的方案数。
设f[i][j][1]表示前i个数，异或和为j，且没选最后一个数的方案数。
转移很简单。。。
#include<cstdio> #include<cctype> #include<queue> #include<cmath> #include<cstring> #include<bitset> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } typedef long long ll; const int maxn=1010; const int maxv=1030; int n,A[maxn]; ll ans,f[maxn][maxv][2],g[maxn][maxv][2]; int main() { n=read();rep(i,1,n) A[i]=read(); rep(i,1,n) { f[i][A[i]][1]++; rep(j,0,1023) { f[i][j^A[i]][1]+=(f[i-1][j][0]+f[i-1][j][1]); f[i][j][0]+=(f[i-1][j][0]+f[i-1][j][1]); } } dwn(i,n,1) { g[i][A[i]][1]++; rep(j,0,1023) { g[i][j&A[i]][1]+=(g[i+1][j][0]+g[i+1][j][1]); g[i][j][0]+=(g[i+1][j][0]+g[i+1][j][1]); } } rep(i,1,n-1) rep(j,0,1023) ans+=(f[i][j][0]+f[i][j][1])*g[i+1][j][1]; printf("%lld ",ans); return 0; }