一眼题
#include<bits/stdc++.h> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define ForkD(i,k,n) for(int i=n;i>=k;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=Pre[x];p;p=Next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=Next[p]) #define Lson (o<<1) #define Rson ((o<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (1000000007) #define pb push_back #define mp make_pair #define fi first #define se second #define vi vector<int> #define pi pair<int,int> #define SI(a) ((a).size()) #define Pr(kcase,ans) printf("Case #%d: %I64d\n",kcase,ans); #define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl; #define PRi2D(a,n,m) For(i,n) { \ For(j,m-1) cout<<a[i][j]<<' ';\ cout<<a[i][m]<<endl; \ } #pragma comment(linker, "/STACK:102400000,102400000") #define ALL(x) (x).begin(),(x).end() typedef long long ll; typedef long double ld; typedef unsigned long long ull; ll mul(ll a,ll b){return (a*b)%F;} ll add(ll a,ll b){return (a+b)%F;} ll sub(ll a,ll b){return ((a-b)%F+F)%F;} void upd(ll &a,ll b){a=(a%F+b%F)%F;} int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();} return x*f; } int main() { // freopen("A.in","r",stdin); // freopen(".out","w",stdout); int n=read(); cout<<(n-1)/2<<endl; return 0; }注意a的数量不变,故倒着贪心一波
#include<bits/stdc++.h> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define ForkD(i,k,n) for(int i=n;i>=k;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=Pre[x];p;p=Next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=Next[p]) #define Lson (o<<1) #define Rson ((o<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (1000000007) #define pb push_back #define mp make_pair #define fi first #define se second #define vi vector<int> #define pi pair<int,int> #define SI(a) ((a).size()) #define Pr(kcase,ans) printf("Case #%d: %I64d\n",kcase,ans); #define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl; #define PRi2D(a,n,m) For(i,n) { \ For(j,m-1) cout<<a[i][j]<<' ';\ cout<<a[i][m]<<endl; \ } #pragma comment(linker, "/STACK:102400000,102400000") typedef long long ll; typedef long double ld; typedef unsigned long long ull; ll mul(ll a,ll b){return (a*b)%F;} ll add(ll a,ll b){return (a+b)%F;} ll sub(ll a,ll b){return ((a-b)%F+F)%F;} void upd(ll &a,ll b){a=(a%F+b%F)%F;} int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();} return x*f; } char s[1123456]; int main() { // freopen("B.in","r",stdin); // freopen(".out","w",stdout); cin>>(s+1); int n=strlen(s+1); ll c=0; ll ans=0; ForD(i,n) { if (s[i]=='b') upd(c,1); else { upd(ans,c); upd(c,c); } } cout<<ans<<endl; return 0; }考虑沿着树贪心的填能填的值中最小的, 可以证明是对的(不会证)。
#include<bits/stdc++.h> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define ForkD(i,k,n) for(int i=n;i>=k;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=Pre[x];p;p=Next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=Next[p]) #define Lson (o<<1) #define Rson ((o<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (1000000007) #define pb push_back #define mp make_pair #define fi first #define se second #define vi vector<int> #define pi pair<int,int> #define SI(a) ((a).size()) #define Pr(kcase,ans) printf("Case #%d: %I64d\n",kcase,ans); #define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl; #define PRi2D(a,n,m) For(i,n) { \ For(j,m-1) cout<<a[i][j]<<' ';\ cout<<a[i][m]<<endl; \ } #pragma comment(linker, "/STACK:102400000,102400000") #define ALL(x) (x).begin(),(x).end() typedef long long ll; typedef long double ld; typedef unsigned long long ull; ll mul(ll a,ll b){return (a*b)%F;} ll add(ll a,ll b){return (a+b)%F;} ll sub(ll a,ll b){return ((a-b)%F+F)%F;} void upd(ll &a,ll b){a=(a%F+b%F)%F;} int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();} return x*f; } int n,m; #define MAXN (312345) int s[MAXN]; vi v[MAXN],e[MAXN]; int ans[MAXN]={}; int chk[MAXN]={}; void dfs(int x,int fa) { //找出这个点上没被染色的点 vi vu; for(auto it:v[x]) { if (ans[it]) chk[ans[it]]=1; else vu.pb(it); } int p=1; for(auto it:vu) { while(chk[p]) ++p; ans[it]=p++; } for(auto it:v[x]) { chk[ans[it]]=0; } for(int v:e[x]) if (v^fa) dfs(v,x); } int main() { // freopen("C.in","r",stdin); n=read(),m=read(); For(i,n) { s[i]=read(); For(j,s[i]) v[i].pb(read()); } For(i,n-1) { int p=read(),q=read(); e[p].pb(q); e[q].pb(p); } dfs(1,0); For(i,m) ans[i]=max(ans[i],1); printf("%d\n",*max_element(ans+1,ans+1+m)); For(i,m) printf("%d ",ans[i]); puts(""); return 0; }暴搜找出 4个一组的换法 5个一组的换法 将2个4个一组交换的方法 然后用这3个方法把答案凑出来
#include<bits/stdc++.h> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define ForkD(i,k,n) for(int i=n;i>=k;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=Pre[x];p;p=Next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=Next[p]) #define Lson (o<<1) #define Rson ((o<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (1000000007) #define pb push_back #define mp make_pair #define fi first #define se second #define vi vector<int> #define pi pair<int,int> #define SI(a) ((a).size()) #define Pr(kcase,ans) printf("Case #%d: %I64d\n",kcase,ans); #define PRi(a,n) For(i,n-1) cout<<a[i]<<' '; cout<<a[n]<<endl; #define PRi2D(a,n,m) For(i,n) { \ For(j,m-1) cout<<a[i][j]<<' ';\ cout<<a[i][m]<<endl; \ } #pragma comment(linker, "/STACK:102400000,102400000") #define ALL(x) (x).begin(),(x).end() typedef long long ll; typedef long double ld; typedef unsigned long long ull; ll mul(ll a,ll b){return (a*b)%F;} ll add(ll a,ll b){return (a+b)%F;} ll sub(ll a,ll b){return ((a-b)%F+F)%F;} void upd(ll &a,ll b){a=(a%F+b%F)%F;} int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();} return x*f; } vector<pair<int,int> > v; void print(int i,int j) { printf("%d %d\n",i+1,j+1); printf("%d %d\n",i+3,j+1); printf("%d %d\n",i+2,j+2); printf("%d %d\n",i+3,j+2); printf("%d %d\n",i+1,j+3); printf("%d %d\n",i+2,j+1); printf("%d %d\n",i+0,j+0); printf("%d %d\n",i+0,j+3); printf("%d %d\n",i+1,j+0); printf("%d %d\n",i+2,j+3); printf("%d %d\n",i+3,j+0); printf("%d %d\n",i+1,j+2); printf("%d %d\n",i+0,j+1); printf("%d %d\n",i+0,j+2); printf("%d %d\n",i+2,j+0); printf("%d %d\n",i+3,j+3); } int main() { // freopen("E.in","r",stdin); // freopen(".out","w",stdout); int n=read(); if (n%4>1) puts("NO"); else { puts("YES"); for(int i=1;i<=n/4*4;i+=4) for(int j=i+4;j<=n/4*4;j+=4) { print(i,j); } for(int i=1;i<=n/4*4;i+=4) { if(n%4) printf("%d %d\n%d %d\n%d %d\n",i+2,n,i+2,i+3,i+3,n); else printf("%d %d\n",i+2,i+3); printf("%d %d\n",i,i+2); printf("%d %d\n",i+1,i+3); printf("%d %d\n",i+1,i+2); printf("%d %d\n",i,i+3); if(n%4)printf("%d %d\n%d %d\n%d %d\n",i,n,i,i+1,i+1,n); else printf("%d %d\n",i,i+1); } } return 0; }