抽屉原理，有时范围并没有看似那么大
抽屉原理
Modulo_Sum
抽屉原理优化
n个数可以产生n个前缀和，这n个前缀和分别对m求余，
得到n个0~m-1范围内的数，若存在前缀和%m==0，必然满足
若不存在，那么n个数落在1~m-1这m-1个数范围中，
相当于n个物品放在m-1个抽屉里，至少有一个抽屉放了两件物品
至少有两个数取了相同的值，那么两个前缀和之间的数可以被m整除
那么，只要n>m,就必然有满足题意的解
#include <bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e6+5;
const int M=1e3+5;
int n,m;
int a[N];
bool dp[M][M];//dp[N][M]会MLE，哪怕是bool型
signed main(){
cin>>n>>m;
if(n>m){
cout<<"YES";
return 0;
}
//所以以下都是n<=m噢，所以可以开m*m大小的空间
for(int i=1;i<=n;i++)cin>>a[i],a[i]%=m;
for(int i=1;i<=n;i++)dp[i][a[i]]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<m;j++){
dp[i][j]|=dp[i-1][j];
dp[i][j]|=dp[i-1][(j-a[i]+m)%m];
}
if(dp[i][0]){
cout<<"YES";
return 0;
}
}
cout<<"NO";
return 0;
}
bitset优化
比普通的bitset优化唯独多了这一句
dp|=(dp>>m);//相当于一个求余的作用，届时只访问dp[m]就好
每次多考虑个t都有超过m的可能，可能没超过m，所以保存dp
可能超过了m,但因为每次都给所有数减去m，所以不可能超过2*m
所有的k*m位置上的1都会保留在m的位置
溢出m*2的k*m不用管
举个例子:
m=5
2 4 3 3 4 4 这个序列的和是20，4*m
但在逐渐累加过程中，保存的过程不是2,6,9,12…
而是
2,
6 1(没错,6还没溢出2000,也会保存下来),
9 4(如果m不是5而是1000，此时的9就会自动消除了),
那么接下来只考虑后者情况(每次对m求余,总在m*2以内)
(4+3)%5=2
(2+4)%5=1
(1+4)=5
#include<bits/stdc++.h>
using namespace std;
const int M=1e3+5;
int n,m;
bitset<2005> dp;//能存下2*m的来过痕迹
signed main(){
cin>>n>>m;
int t;
dp[0]=1;
// if(n>m){//不用抽屉原理优化也能过
// cout<<"YES";
// return 0;
// }
for(int i=1;i<=n;i++){
cin>>t;
t%=m;
if(t==0){//不可少，m=5，假设给的序列为5 2 4，
// 虽是如此，直接给t求余，就将5变成了0，没了在bitset中保存5的机会
// 掐掉了yes的唯一可能
cout<<"YES";
return 0;
}
dp=dp|(dp<<t);
dp|=(dp>>m);//相当于一个求余的作用，届时只访问dp[m]就好
}
if(dp[m])cout<<"YES";
else cout<<"NO";
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int maxm=1e3+5;
int n, m;
bitset<1000> f;
int main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i=1; i<=n; i++){
int t; cin >> t; t %= m;
if(t==0){
cout<<"YES";
return 0;
}
f = f | (f<<t);
f[t] = 1;
}
/* 在未涉及到对m求余，而是简单地问是否能组成m，就无需f>>(m-t)
有何用途呢？之前只需要一味累加，看能否得到m
现在累加得到的如果是m的若干倍也行，而ai数量级又是1e9，
累加的和天知道是m的多少倍，就无法通过查询f[k*m]来得知是否有结果
也就是f<<t可能会超过m，然后无法保留k*m位置上的1
那么就需要
m=5;
t=3
f里面的2ok，7也ok
(f>>(m-t)),想必这一条也是防止t==0,不止
*/
for(int i=0; i<1000; i+=m){
if(f[i]) {cout<<"YES"; return 0;}
}
cout<<"NO";
}
选数
-
1、完全背包双重循环，1e10，超时
d p [ i ] [ j ] ∣ = d p [ i ? 1 ] [ j ] ; dp[i][j]|=dp[i-1][j]; dp[i][j]∣=dp[i?1][j];
d p [ i ] [ j ] ∣ = d p [ i ? 1 ] [ ( j ? a [ i ] + n ) dp[i][j]|=dp[i-1][(j-a[i]+n)%n]; dp[i][j]∣=dp[i?1][(j?a[i]+n) -
2、bitset优化，难以输出路径(选取的数)
-
3、根据Modulo Sum这题，考虑是否有子序列和满足 对n求余为0
首先预处理出前缀和，n个前缀和，对n分别求余有n种余数，落在0~n-1 -
若余数为0，显然有连续的子序列满足条件，从下标1输出就好
-
若不存在余数为0，根据抽屉原理，必定存在至少两个前缀和对应相同的余数
两个前缀和之间的连续的数 即为所求，也容易输出
很容易发现，总会有连续的子序列符合答案，因为连续十分容易输出
当然了，不连续的也是存在的 ，比如样例给出的
//#include <bits/stdc++.h>
#include <iostream>
using namespace std;
const int N=1e5+5;
int a[N];
int n;
int s[N];
int pre[N];//之前是否已经存在某个前缀和,既指示非零下标又判断是否出现过
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
s[0]=0;
for(int i=1;i<=n;i++){
cin>>a[i],a[i]%=n;
s[i]=(s[i-1]+a[i]+n)%n;
}
for(int i=1;i<=n;i++){
if(s[i]==0){
cout<<i<<endl;
for(int j=1;j<=i;j++)cout<<j<<" ";
return 0;
}
}
for(int i=1;i<=n;i++){
if(!pre[s[i]])pre[s[i]]=i;//既指示非零下标又判断是否出现过
else{
int p=pre[s[i]];
cout<<i-p<<endl;//从p+1开始的
for(int j=p+1;j<=i;j++)cout<<j<<" ";
return 0;
}
}
return 0;
}
XOR-gun(思维+异或前缀和+暴力)
首先要知道一个很重要的性质，对于非降序的序列最高位的二进制1的位置也一定是非降序的，如果存在3个连续的数最高位1位置相同，只需要将后两个数异或就一定小于第一个数(使得最高位变为0)
根据抽屉原理(更感觉是逆着想)，如果不存在连续的3个数最高位相同
0 1 10 11 100 101 110(不允许) 1000 1001 10010 10110……
对于二进制数位数为m位的数，最多只能取2个
也即是:
如果不存在连续的3个数最高位相同,
则该序列长度不超过
2
?
(
a
i
可
能
的
位
数
)
2*(ai可能的位数)
2?(ai可能的位数)
而
a
[
i
]
a[i]
a[i]的范围是
1
e
9
1e9
1e9,
l
o
g
2
(
1
0
9
)
<
30
log_2(10^9)<30
log2?(109)<30，这个范围最多有30位
1024
?
1024
?
1024
>
1
e
9
1024*1024*1024>1e9
1024?1024?1024>1e9
至于小于60个数，只需要三重循环枚举两个相邻块的异或结果进行比较就好了
//#include <bits/stdc++.h>
#include <iostream>
using namespace std;
const int N=1e5+5;
int n;
int a[N];
int sum[N];//异或前缀和
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
sum[0]=0;//任何数异或0得到原数
for(int i=1;i<=n;i++)cin>>a[i],sum[i]=sum[i-1]^a[i];
if(n>60)cout<<"1";
else{//是否存在[l,i]>[i+1,r]
int res=0x3f3f3f3f;
for(int i=1;i<=n-1;i++){
for(int l=1;l<=i;l++){
for(int r=i+1;r<=n;r++){
int x=sum[i]^sum[l-1];
int y=sum[r]^sum[i];
if(x>y){
// cout<<r-l-1;
// return 0;
// 1 2 3 4 5
res=min(res,r-l-1);
}
}
}
}
if(res<0x3f3f3f3f)cout<<res;
else cout<<"-1";
}
return 0;
}
