第一课: 枚举
A.给你一个棋盘..每次操作可以使一个点自身以及上下左右改变颜色...,(只有两种颜色类似二进制),最少几次操作可以使棋盘同色[编辑]
裸的暴搜枚举,
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; char a[10][10]; int ans=999999; int change(int num){ int x = num/4,y = num%4; if(x!=0)a[x-1][y] = (a[x-1][y]=='w')?'b':'w'; if(y!=0)a[x][y-1] = (a[x][y-1]=='w')?'b':'w'; if(x!=3)a[x+1][y] = (a[x+1][y]=='w')?'b':'w'; if(y!=3)a[x][y+1] = (a[x][y+1]=='w')?'b':'w'; a[x][y] = (a[x][y]=='w')?'b':'w'; return 0; } bool check(){ char p = a[0][0]; for(int i=0;i<4;i++){ for(int j=0;j<4;j++){ if(a[i][j]!=p)return false; } } return true; } int main(){ for(int i=0;i<4;i++)cin>>a[i]; for(int i=0;i<(1<<16);i++){ int tmp = 0; for(int j=0;j<16;j++)if(((1<<j)&i)!=0)tmp++,change(j); if(check()==true)ans = min(ans,tmp); for(int j=0;j<16;j++)if(((1<<j)&i)!=0)change(j); } if(ans==999999)cout<<"Impossible"<<endl; cout<<ans<<endl; }
B.双指针裸题...给你一段数组求找到最短的一段连续的字段使其大于等于K
直接双指针怼上去上去
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int n,m,a[100005],ans; int main(){ a[0] = 0; while(scanf("%d%d",&n,&m)==2){ ans = 999999; for(int i=1;i<=n;i++)cin>>a[i]; int j=0,now=0; for(int i=1;i<=n;i++){ while(now<m&&j<n)now+=a[j+1],j++; if(now>=m)ans = min(ans,j-i+1); now-=a[i]; } if(ans==999999)cout<<0<<endl; else cout<<ans<<endl; } }
C.求多少区间异或总和等于区间和
嘛,把异或当成奇数偶数个2的n次幂 然后就没了... 主要知道当a,b(a+b>a^b)同时存在所选的一段区间时,只有a,b去掉一个,这个区间才有可能满足题意 结论题真有意思 跟ATCODER GRAND 3 的E题很像(思想上)...
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; long long n,a[300005],ans=0; int main(){ cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; int j=0,now=0,pp=0; for(int i=1;i<=n;i++){ while((pp^a[j+1])==now+a[j+1]&&j<n){ now+=a[j+1]; pp = pp^a[j+1]; j++; } if(pp==now)ans+=(j-i+1); now-=a[i]; pp = pp^a[i]; } cout<<ans<<endl; }
D.裸的折半枚举
首先考虑2的35次方会t飞 而后想到同余求和的集合可加性 然后就自然的想到二进制枚举高出答案然后*(再2的二分之N次方)*(log2的二分之N次方) 解决问题....感觉要写寒假作业..(不然不好交代)
#include<bits/stdc++.h> using namespace std; int n; long long m,a[45],b[45],c[1000005],d[1000005]; long long tot1=0,tot2=0,ans=0; bool cmp(long long x,long long y){return x<y; } int main(){ cin>>n>>m; for(int i=1;i<=n/2;i++)cin>>a[i]; for(int i=n/2+1;i<=n;i++)cin>>b[i]; int jiexian = n/2; for(int i=0;i<(1<<jiexian);i++){ long long sum=0; for(int j=0;j<=jiexian;j++) if(((1<<j)&i)!=0) sum=(sum%m+a[j+1]%m)%m; tot1++; c[tot1] = sum%m; } for(int i=0;i<(1<<(n-jiexian));i++){ long long sum=0; for(int j=jiexian+1;j<=n;j++) if(((1<<(j-jiexian-1))&i)!=0) sum=(sum%m+b[j]%m)%m; tot2++; d[tot2] = sum%m; } sort(c+1,c+1+tot1,cmp); sort(d+1,d+1+tot2,cmp); ans = max(c[tot1],d[tot2]); for(int i=1;i<=tot1;i++){//找最接近m-1-c[i] int l=1,r=tot2,mid; while(l<=r){ mid = (l+r)>>1; if(d[mid]<=(m-1-c[i]))l = mid+1,ans=max(ans,d[mid]+c[i]); else r = mid-1; } } cout<<ans<<endl; }
A.给你一个棋盘..每次操作可以使一个点自身以及上下左右改变颜色...,(只有两种颜色类似二进制),最少几次操作可以使棋盘同色[编辑]
裸的暴搜枚举,
1
2 #include<iostream>
3 #include<cstdio>
4 #include<algorithm>
5 using namespace std;
6
7 char a[10][10];
8 int ans=999999;
9
10 int change(int num){
11 int x = num/4,y = num%4;
12 if(x!=0)a[x-1][y] = (a[x-1][y]=='w')?'b':'w';
13 if(y!=0)a[x][y-1] = (a[x][y-1]=='w')?'b':'w';
14 if(x!=3)a[x+1][y] = (a[x+1][y]=='w')?'b':'w';
15 if(y!=3)a[x][y+1] = (a[x][y+1]=='w')?'b':'w';
16 a[x][y] = (a[x][y]=='w')?'b':'w';
17 return 0;
18 }
19
20 bool check(){
21 char p = a[0][0];
22 for(int i=0;i<4;i++){
23 for(int j=0;j<4;j++){
24 if(a[i][j]!=p)return false;
25 }
26 }
27 return true;
28 }
29
30 int main(){
31 for(int i=0;i<4;i++)cin>>a[i];
32 for(int i=0;i<(1<<16);i++){
33 int tmp = 0;
34 for(int j=0;j<16;j++)if(((1<<j)&i)!=0)tmp++,change(j);
35 if(check()==true)ans = min(ans,tmp);
36 for(int j=0;j<16;j++)if(((1<<j)&i)!=0)change(j);
37 }
38 if(ans==999999)cout<<"Impossible"<<endl;
39 cout<<ans<<endl;
40 }