【题目描述】 你手上有 N 个非负整数, 你需要在这些数中找出一个非空子集, 使得它的元素之和能被N 整除. 如果有多组合法方案, 输出任意一组即可. 注意: 请使用高效的输入输出方式避免输入输出耗时过大.
【输入格式】 第一行一个整数 N, 代表数字个数. 接下来一行 N 个数, 代表你手上的数.
【输出格式】 如果无解, 输出-1. 否则, 第一行输出一个整数 M, 代表你选择的数的个数. 接下来一行 M 个数, 代表你选中元素的下标, 这 M 个数必须两两不同.
没有想到前缀和，想到了就是一道大水题。（雾
应该人人都会想到在输入时对一个数取模后再存到桶里面吧。但是这样只能搜索，T飞。加上我的迭代加深都只有70分。
显然这道题是不会出现无解的情况的，可以考虑前缀和，把输入的数加在前缀和里面，对 n n n取模后再存到桶里面。因为有 n n n个数，而前缀和只有 n − 1 n-1 n−1种情况，所以必定会出现两个前缀和 i i i和 j j j，使 s u m [ i ] = = s u m [ j ] sum[i]==sum[j] sum[i]==sum[j]。根据模数的定义， s u m [ i ] − s u m [ j ] = = 0 sum[i]-sum[j]==0 sum[i]−sum[j]==0，即 i + 1 i+1 i+1 ~ j j j中的数的和模 n n n等于0，符合题意，所以直接输出 i + 1 i+1 i+1 ~ j j j就好了。
虐我智商。
70分迭代加深
#include<cstdio> #include<algorithm> #define ll long long #define maxn 1000005 using namespace std; struct node { int v,next; }tr[maxn]; int n,fl; int tot,head[maxn],cnt[maxn],ans[maxn]; ll sum[maxn];//前缀和 ll read() { ll ret=0,fl=1; char ch; while((ch=getchar())<'0'||ch>'9') { if(ch=='-') fl=-1; } ret=ch-'0'; while((ch=getchar())>='0'&&ch<='9') ret=(ret<<3)+(ret<<1)+ch-'0'; return ret*fl; } void print(ll x) { if(x<0) { putchar('-'); x=-x; } if(x>9) print(x/10); putchar(x%10+'0'); } void printans(int x) { print(x); putchar('\n'); for(int i=1;i<=x;++i) { print(ans[i]); putchar(' '); } } ll gcd(int x,int y) { return (!y)?x:gcd(y,x%y); } void add(int x,int y) { tot++; tr[tot].v=y; tr[tot].next=head[x]; head[x]=tot; cnt[x]++;//记录模数个数 } void dfs(int all,int lst,ll ret)//总共搜索的数的个数,上一次搜索的模数,还剩的数 { if(ret==0) { fl=1; printans(all); return;//搜完了 } if(sum[lst]<ret)return;//剪枝 int nxt=lst; while((!cnt[nxt]||nxt>ret)&&nxt>0)nxt--; if(nxt==0)return; int mx=min(ret/nxt,(ll)cnt[nxt]),allnxt=all+1; for(int t=head[nxt];t&&allnxt<=all+mx;t=tr[t].next) { int y=tr[t].v; ans[allnxt]=y; allnxt++; }//提前记录答案 for(int i=mx;i>=1;--i) { allnxt--; dfs(allnxt,nxt-1,ret-i*nxt); } } int main() { freopen("set.in","r",stdin); freopen("set.out","w",stdout); n=read(); for(int i=1;i<=n;++i) { ll x=read(); add(x%n,i); } if(cnt[0]) { int ans=tr[head[0]].v; print(1); putchar('\n'); print(ans); return 0; }//特判模数为0 for(int i=1;i<n;++i) { int x=gcd(n,i),y; y=n/x; if(cnt[i]>=y) { print(y); putchar('\n'); int nw=1; for(int t=head[i];t&&nw<=y;t=tr[t].next) { int z=tr[t].v; print(z); putchar(' '); nw++; } fl=1; } if(fl) return 0; }//特判倍数 for(int i=0;i<n;++i) sum[i]=sum[i-1]+cnt[i]*i;//计算模数前缀和 for(int i=1;i<=n;++i)//枚举搜索的倍数,迭代加深 { fl=0; dfs(0,n-1,n*i); if(fl)break; } return 0; }正解
#include<cstdio> #define ll long long #define maxn 100005 using namespace std; ll n,fl; ll sum[maxn],tong[maxn]; void print(ll x,ll y) { printf("%lld\n",y-x); for(int i=x+1;i<=y;++i) printf("%lld ",i); } int main() { freopen("set.in","r",stdin); freopen("set.out","w",stdout); scanf("%lld",&n); for(int i=1;i<=n;++i) { ll x; scanf("%lld",&x); if(x%n==0) { printf("1\n%lld",i); fl=1; } sum[i]=(sum[i-1]+x)%n; } if(fl)return 0; for(int i=1;i<=n;++i) { if(tong[sum[i]]) { print(tong[sum[i]],i); break; } else tong[sum[i]]=i; } return 0; }【题目描述】 热爱看书的你有 N 本书, 第 i 本书的种类为 A[i]. 你希望每天能够看一本书, 但是不希望 连续两天看种类相同的书. 为了达成这个条件, 你需要选择一些书不看, 作为一个好学生, 你 希望不看的书尽可能少, 求最少可以有多少书不看.
【输入格式】 为了避免输入文件过大, 我们采取如下方式生成 A[i]. 第一行读入两个个整数 M, K. 接下来一行读入 M 个整数 count[i], 其中𝑁 = ∑ 𝑐𝑜𝑢𝑛𝑡[𝑖]. 接下来一行读入 M 个整数 X[i]. 接下来一行读入 M 个整数 Y[i]. 接下来一行读入 M 个整数 Z[i]. 然后按照下面这段代码生成.
int N = 0, S = (1 << K) - 1; for (int i = 1; i <= M; ++i) { N = N + 1; A[N] = X[i]; long long last = X[i]; for (int j = 1; j < count[i]; ++j) { last = (last * Y[i] + Z[i]) & S; N = N + 1; A[N] = last; } }注意:因为生成 A[i]的方法不好用语言描述, 所以用代码来表达. 直接照搬代码的话后果自负.
【输出格式】 输出一个整数表示答案.
一道我想了一个多小时的水题。
若贪心地想，为了避免相邻种类重复，对于同一个种类，明显应该各一个放一个。所以，若一个种类的个数小于总数的一半，那么这些数一定不会计入答案，若有一个种类的数超过了总数的一半，那么这个种类一定会有一些数计入答案，那么其它种类的个数一定小于总数的一半，一定不会计入答案。
所以我们可以记录众数，看众数的个数有没有大于 n 2 \frac{n}{2} 2n。
如何统计众数？空间限制只有16M，最多只能开400万的数组。
考虑以前用过的一种方法，设 l s t lst lst表示当前的众数， t o t tot tot表示当前众数的个数，遇到与 l s t lst lst相等的数， t o t tot tot加1，否则 t o t tot tot减1，当 t o t tot tot等于0时更新 l s t lst lst为当前数，同时 t o t tot tot赋值为1.举个例子，设当数列为：
2,1,1,2,1,3,1,1,4
跑下来的 t o t tot tot和 l s t lst lst分别为：
lst: 2, 1, 1, 1, 1, 1, 1, 1, 1 tot:1, 1, 2, 1, 2, 1, 2, 3, 2
最后求出来的众数就是 1 1 1。
但是这个方法只对众数个数大于 n 2 \frac{n}{2} 2n有用，当众数不大于 n 2 \frac{n}{2} 2n时，此方法不再适用，例如：
1,1,2,2,3,3,1
跑下来的 t o t tot tot和 l s t lst lst分别为：
lst: 1, 1, 1, 2, 2, 2, 3, 3, 3 tot: 1, 2, 1, 1, 2, 1, 1, 2, 1
这样就出现了问题。
怎么办呢？因为这道题只是求区间众数是否大于 n 2 \frac{n}{2} 2n，所以我们还可以再扫一遍。当我们求出 l s t lst lst后，再扫一遍，统计 l s t lst lst的个数，若 l s t lst lst小于 n 2 \frac{n}{2} 2n，那么所有的数都可以选，否则统计答案为 s u m − ( n − s u m + 1 ) sum-(n-sum+1) sum−(n−sum+1)。
【题目描述】 一年一度的运动会开始了. 有 N 个选手参赛, 第 i 个选手有一个能力值 A[i](保证 A[i]两两不同), 比赛一共进行了 2 m 2^m 2m天. 在第 j 天(0 ⩽ 𝑗 ⩽ 2 m − 1 2^m − 1 2m−1)的比赛中, 第 i 个选手的得分为 A[i] xor j, 然后从大到小排名, 排名为 x(x 从 0 开始)的同学会获得𝑥2的积分, 你需要求出每个同学最后总的积分和 q[i]模 1 0 9 + 7 10^9 + 7 109+7的结果 p[i]. 为了避免输出文件过大, 你只要输出 p[i]的异或和即可.
【输入格式】 第一行三个整数, 分别代表 N, M. 接下来一行 N 个整数, 第 i 个数代表 A[i].
【输出格式】 一个整数代表答案.
【数据范围】 对于 10%的数据, M <= 5. 对于 30%的数据, N <= 100. 对于 50%的数据, N <= 1000. 对于 100%的数据, N <= 200000, M <= 30, A[i] < 2 m 2^m 2m.
一道思维好题。
本题的突破口在于m的范围，m最大为30，而 2 30 = 1073741824 2^{30}=1073741824 230=1073741824，显然枚举天数是肯定会 T L E TLE TLE的。
再看j的范围 0 ≤ j ≤ 2 m − 1 0\leq j\leq 2^m-1 0≤j≤2m−1，即在二进制数下 0 ≤ j ≤ 111 ⋯ 111 0\leq j\leq 111\cdots111 0≤j≤111⋯111，即对于二进制数下前m位，每一位都可以取0或1.又因为这道题是异或，所以 A [ i ] A[i] A[i]的每一位都可以异或0或者异或1.
再来考虑异或的性质。若两个数前k-1位已经相同了，i的第k位是0，j的第k位是1.那么当两个数异或1时，i大于j，反之i小于j。这对答案的统计十分重要。
那么如何保证前k位完全相同呢？因为二进制数下每个数位只能是0或者1，所以可以把 A A A数组存进 T r i e Trie Trie树里面，记录经过每个节点的数的个数。
void insert(ll x) { int p=0; for(int i=m-1;i>=0;--i) { int y=(x>>i)&1; if(!tri[p][y])tri[p][y]=++cnt;//动态开点 size[tri[p][y]]++; p=tri[p][y]; } }然后从根节点开始搜索，设状态为 d f s ( p , s u m , n u m ) dfs(p,sum,num) dfs(p,sum,num)，表示当前遍历到 T r i e Trie Trie树中的节点 p p p，当前的答案 a n s ans ans，比当前节点小的数的个数 n u m num num，当 t r i [ p ] [ 0 ] tri[p][0] tri[p][0]不为0时，说明这一位为0的数的个数不为0.那么当当前异或的值是1时， t r i [ p ] [ 1 ] tri[p][1] tri[p][1]中的所有数都比 t r i [ p ] [ 0 ] tri[p][0] tri[p][0]中的所有数小，这时统计答案。又因为有 2 m − 1 2^{m-1} 2m−1时当前异或的值为1，所以答案还要乘以 2 m − 1 2^{m-1} 2m−1，记录 n u m num num，再往下搜索：
int x=tri[p][0],y=tri[p][1]; if(x) dfs(x,(sum+size[y]*size[y]%mod*(1<<(m-1))%mod+size[y]*num%mod*(1<<(m-1))%mod)%mod,num+size[y]);//有一定的概率0^1=1当 t r i [ p ] [ 1 ] tri[p][1] tri[p][1]不为0时同理：
if(y) dfs(y,(sum+size[x]*size[x]%mod*(1<<(m-1))%mod+size[x]*num%mod*(1<<(m-1))%mod)%mod,num+size[x]);最后，若 t r i [ p ] [ 0 ] tri[p][0] tri[p][0]和 t r i [ p ] [ 1 ] tri[p][1] tri[p][1]都为0时，说明已经到底了，这时统计最终结果，即 a n s = a n s x o r s u m ans =ans\ xor\ sum ans=ans xor sum，回溯。
