抽屉原理,有时范围并没有看似那么大

抽屉原理

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 这个序列的和是204*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[i1][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[i1][(ja[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

102410241024>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;
}