| 小象涂色 |
| 难度级别：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=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
double f[][];
int n,c,k,cnt[];
int main() {
dwn(T,read(),) {
n=read();c=read();k=read();
memset(f,,sizeof(f));
memset(cnt,,sizeof(cnt));
f[][]=;
rep(t,,k-) rep(j,,c-) {
f[t+][j]+=f[t][j]*0.5;
rep(k,,c-) f[t+][(j*k)%c]+=f[t][j]*(0.5/c);
}
double ans=;
rep(i,,k) {
int l=read(),r=read();
rep(j,l,r) cnt[j]++;
}
rep(i,,n) rep(j,,c-) ans+=f[cnt[i]][j]*j;
printf("%.9lf\n",ans);
}
return ;
}
| 行动！行动！ |
| 难度级别：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=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
const int maxm=;
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[][maxn],done[maxn*];
priority_queue<HeapNode> Q;
void spfa() {
rep(i,,k) rep(j,,n-) d[i][j]=<<;
Q.push((HeapNode){s+n*k,});d[k][s]=;
while(!Q.empty()) {
if(done[Q.top().u]) {Q.pop();continue;}
else done[Q.top().u]=;
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-][to[i]]>d[k2][x]) {
d[k2-][to[i]]=d[k2][x];
Q.push((HeapNode){to[i]+n*k2-n,d[k2-][to[i]]});
}
}
}
}
int main() {
n=read();m=read();k=read();
s=read();t=read();
rep(i,,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=<<;
rep(i,,k) ans=min(ans,d[i][t]);
printf("%d\n",ans);
return ;
}
| 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=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
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,,T) {
printf("Case %d:\n",Case);
int n=read(),m=read();
rep(i,,n) pa[i]=i,s[i]=,d[i]=;
rep(i,,m) {
char cmd[];scanf("%s",cmd);
if(cmd[]=='Q') {
int y,x=findset(y=read());
printf("%d %d %d\n",x,s[x],d[y]);
}
else {
int x=findset(read()),y=findset(read());
pa[x]=y;s[y]+=s[x];d[x]++;
}
}
}
return ;
}
| 挖掘机 |
| 难度级别：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=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
typedef long long ll;
const int maxn=;
int A[maxn],B[maxn],n1,n2;
char s[];
int main() {
int n=read(),m=read();
rep(i,,n) {
scanf("%s",s);
if(s[]=='T') A[++n1]=read();
else B[++n2]=read();
}
B[++n2]=m;
sort(A+,A+n1+);sort(B+,B+n2+);
double ans=,p=0.0;int c=,cur=;
rep(i,,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\n",(ll)ans);
return ;
}
| 藏宝图 |
| 难度级别：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=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
struct Edge {
int u,v;ll w;
bool operator < (const Edge& ths) const {return w<ths.w;}
}E[maxn*maxn/];
ll d[maxn][maxn];
int n,pa[maxn],first[maxn],next[maxn<<],to[maxn<<],dis[maxn<<],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,,sizeof(vis));
Q.push(x);vis[x]=;dist[x]=;
while(!Q.empty()) {
x=Q.front();Q.pop();
ren if(!vis[to[i]]) {
vis[to[i]]=;
dist[to[i]]=dist[x]+dis[i];
Q.push(to[i]);
}
}
}
int main() {
dwn(T,read(),) {
n=read();int m=;e=;memset(first,,sizeof(first));
rep(i,,n) rep(j,,n) d[i][j]=read();
rep(i,,n) {
pa[i]=i;int best=;
rep(j,,n) if(i<j) E[++m]=(Edge){i,j,d[i][j]};
}
sort(E+,E+m+);
rep(i,,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=;
rep(i,,n) {
bfs(i);
rep(j,,n) if(d[i][j]!=dist[j]) ok=;
}
if(!ok) puts("No");
else {
puts("Yes");
if(n==) puts("");
else {
int ans=;double mx=0.0;
rep(x,,n) {
int cnt=;double val=;
ren cnt++,val+=dis[i];
val/=cnt;if(val>mx) mx=val,ans=x;
}
printf("%d\n",ans);
}
}
}
return ;
}
| 最大公约数 |
| 难度级别：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=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
int S[maxn],ans;
int main() {
int n=read(),k=read();
rep(i,,n) S[read()]++;
rep(i,,) {
int cnt=;
for(int j=i;j<=;j+=i) cnt+=S[j];
if(cnt>=k) ans=max(ans,i);
}
printf("%lld\n",(long long)ans*k);
return ;
}
| 密码 |
| 难度级别：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=;
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=;
for(;x;x-=x&-x) res+=c[x];
return res;
}
int main() {
scanf("%lld%s",&m,s+);n=strlen(s+);
dwn(i,n,) next[i]=first[s[i]-'a'],first[s[i]-'a']=i,add(i,);
rep(i,,n) {
int j=,tmp;
for(;j<=;j++) if(first[j]&&(tmp=sum(first[j]-))<=m) {
m-=tmp;add(first[j],-);first[j]=next[first[j]];break;
}
putchar(j+'a');
}
return ;
}
| 取数 |
| 难度级别：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=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
int A[],n;
int main() {
n=read();
rep(i,,n) A[i]=read();
int r=n,l=;
while(A[r]) r--;
while(A[l+]) l++;
r=n-r;
if(l&||r&) puts("YES");
else puts("NO");
return ;
}
| 游戏 |
| 难度级别：C； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
|
试题描述
|
|
windy学会了一种游戏。 如： 1 2 3 4 5 6 这时，我们就有若干排1到N的排列，上例中有7排。 |
|
输入
|
|
输入文件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=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
typedef long long ll;
const int maxn=;
int vis[maxn],p[maxn],n,cnt;
ll ans,f[][maxn];
void init() {
rep(i,,n) if(!vis[i]) {
p[++cnt]=i;
for(int j=i*i;j<=n;j+=i) vis[j]=;
}
}
int main() {
n=read();init();
f[][]=;
rep(i,,cnt) {
rep(j,,n) f[i][j]=f[i-][j];
for(int j=p[i];j<=n;j*=p[i]) rep(k,,n-j) f[i][j+k]+=f[i-][k];
}
rep(i,,n) ans+=f[cnt][i];
printf("%lld\n",ans);
return ;
}
| 迎接仪式 |
| 难度级别：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=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
const int maxk=;
char s[maxn];
int f[maxn][maxk][maxk],ans;
int main() {
int n=read(),m=read();scanf("%s",s+);
rep(i,,n) rep(x,,m) rep(y,,m) {
f[i][x][y]=f[i-][x][y];
int t1=s[i-]=='z',t2=s[i]=='j';
if(x>=t1&&y>=t2) f[i][x][y]=max(f[i][x][y],f[i-][x-t1][y-t2]+);
if(x==y) ans=max(ans,f[i][x][y]);
}
int cnt1=,cnt2=;
rep(i,,n) cnt1+=s[i]=='j',cnt2+=s[i]=='z';
printf("%d\n",min(ans,min(cnt1,cnt2)));
return ;
}
| 连连看 |
| 难度级别：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=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
char Map[][];
const int mx[]={,-,,};
const int my[]={,,-,};
int n,m,vis[][][][];
string ans;
int dfs2(int x,int y,int x1,int y1,int dir,int t) {
if(vis[x][y][dir][t]) return ;vis[x][y][dir][t]=;
if(t>) return ;
if(x==x1&&y==y1) return ;
int nx=x+mx[dir],ny=y+my[dir];
if(nx>=&&ny>=&&nx<=n+&&ny<=m+&&!Map[nx][ny]) if(dfs2(nx,ny,x1,y1,dir,t)) return ;
rep(ndir,,) if(dfs2(x,y,x1,y1,ndir,t+)) return ;
return ;
}
int check(int x1,int y1,int x2,int y2) {
rep(dir,,) {
memset(vis,,sizeof(vis));
if(dfs2(x1,y1,x2,y2,dir,)) return ;
}
return ;
}
void dfs(int cur,int final,string cd) {
if(cur==final) ans=min(ans,cd);
else {
rep(x,,n) rep(y,,m) rep(nx,,n) rep(ny,,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]=;
if(check(x,y,nx,ny)) dfs(cur+,final,cd+c);
Map[nx][ny]=Map[x][y]=c;
}
}
}
int main() {
n=read();m=read();
if(n*m&) puts("Game over.");
else {
rep(i,,n) scanf("%s",Map[i]+);
rep(j,,m+) Map[][j]=Map[n+][j]=;
rep(j,,n+) Map[j][]=Map[j][m+]=;
ans="ZZZZZZZ";dfs(,n*m/,"");
if(ans=="ZZZZZZZ") puts("Game over.");
else cout<<ans<<endl;
}
return ;
}
| 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=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
int first[maxn],next[maxn<<],to[maxn<<],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][];
int dp(int x,int tp,int fa) {
int& ans=f[x][tp];
if(ans>=) return ans;
ans=;
if(!tp) {
int v1=,v2=;
ren if(to[i]!=fa) {
v1+=dp(to[i],,x);
v2+=dp(to[i],,x);
}
ans=max(v1,v2+);
}
else ren if(to[i]!=fa) ans+=dp(to[i],,x);
return ans;
}
int main() {
memset(f,-,sizeof(f));
int n=read();
rep(i,,n) AddEdge(read()+,read()+);
printf("%d\n",dp(,,-));
return ;
}
| 机房人民大团结 |
| 难度级别：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=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
typedef long long ll;
const int maxn=;
int n,m,A[maxn];
ll f[maxn][maxn],g[maxn][maxn];
int main() {
n=read();m=read()+;
rep(i,,n) A[i]=read();
rep(l,,n) {
ll val=;
rep(r,l,n) val+=A[r],g[l][r]=g[l][r-]+val;
}
rep(i,,n) f[][i]=1ll<<;
rep(i,,n) {
f[i][]=g[][i];
rep(j,,i) {
f[i][j]=1ll<<;
rep(k,j-,i-) f[i][j]=min(f[i][j],f[k][j-]+g[k+][i]);
}
rep(j,i+,n) f[i][j]=1ll<<;
}
printf("%lld\n",f[n][m]);
return ;
}
| 四轮车 |
| 难度级别：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=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
const int HASH=;
struct Hash_Map {
int x[maxn],y[maxn],cnt[maxn],next[maxn],n;
int first[HASH];
void init() {
memset(first,,sizeof(first));
memset(cnt,,sizeof(cnt));
n=;
}
void insert(int X,int Y) {
int p=(X*Y)%HASH;if(p<) p+=HASH;
ren if(x[i]==X&&y[i]==Y) {cnt[i]++;return;}
x[++n]=X;y[n]=Y;cnt[n]=;next[n]=first[p];first[p]=n;
}
int query(int X,int Y) {
int p=(X*Y)%HASH;if(p<) p+=HASH;
ren if(x[i]==X&&y[i]==Y) return cnt[i];
return ;
}
}S;
int n,x[maxn],y[maxn];
int solve() {
S.init();int res=;
rep(i,,n) S.insert(x[i],y[i]);
rep(i,,n) rep(j,i+,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,,n) x[i]=read(),y[i]=read();
int ans=solve();
rep(i,,n) {
int a=x[i],b=y[i];
x[i]=a+b;y[i]=a-b;
}
printf("%d\n",ans+solve());
return ;
}
| 盘子序列 |
| 难度级别：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=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
int n,top,A[maxn],T[maxn],S[maxn];
int main() {
while(scanf("%d",&n)==) {
rep(i,,n) T[i]=A[i]=read();
sort(T+,T+n+);
rep(i,,n) A[i]=lower_bound(T+,T+n+,A[i])-T;
int cur=;top=;
rep(i,,n) {
S[++top]=i;
while(top&&S[top]==A[cur]&&cur<=n) top--,cur++;
}
puts(top?"J":"Y");
}
return ;
}
| 点名 |
| 难度级别：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=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
struct Node {
Node* ch[];
int r,s;
ll v;
void maintain() {s=ch[]->s+ch[]->s+;}
}nodes[maxn],*null=&nodes[];
int ToT;
Node* newnode(ll v) {
Node* o=&nodes[++ToT];
o->v=v;o->ch[]=o->ch[]=null;o->s=;o->r=rand();
return o;
}
void rotate(Node* &o,int d) {
Node* k=o->ch[d^];o->ch[d^]=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^);
else o->maintain();
}
}
ll query(Node* &o,ll k) {
if(k>o->s) return -;
if(o->ch[]->s+==k) return o->v;
if(o->ch[]->s>=k) return query(o->ch[],k);
return query(o->ch[],k-o->ch[]->s-);
}
void print(Node* &o) {
if(o==null) return;
print(o->ch[]);
printf("%d ",o->v);
print(o->ch[]);
}
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,,n) Q[i]=(Operation){,i,,read()};
rep(i,,m) Q[i+n]=(Operation){,read(),i,i};
n+=m;sort(Q+,Q+n+);
rep(i,,n) {
if(!Q[i].type) insert(root,Q[i].v);
else ans[Q[i].id]=query(root,Q[i].v);
}
rep(i,,m) printf("%lld\n",ans[i]);
return ;
}
| 序列问题 |
| 难度级别：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=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
typedef long long ll;
const int maxn=;
const int maxv=;
int n,A[maxn];
ll ans,f[maxn][maxv][],g[maxn][maxv][];
int main() {
n=read();rep(i,,n) A[i]=read();
rep(i,,n) {
f[i][A[i]][]++;
rep(j,,) {
f[i][j^A[i]][]+=(f[i-][j][]+f[i-][j][]);
f[i][j][]+=(f[i-][j][]+f[i-][j][]);
}
}
dwn(i,n,) {
g[i][A[i]][]++;
rep(j,,) {
g[i][j&A[i]][]+=(g[i+][j][]+g[i+][j][]);
g[i][j][]+=(g[i+][j][]+g[i+][j][]);
}
}
rep(i,,n-) rep(j,,) ans+=(f[i][j][]+f[i][j][])*g[i+][j][];
printf("%lld\n",ans);
return ;
}