A题 模拟
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int mod1=1e9+7; const int mod2=1e9+9; int base=11; struct X{ int x,y; int x1,y1; }; struct node{ X s[11]; int cnt; int g[10][10]; }tmp; map<ll,int> m1; int g[10][10]; int mx; bool check(node x){ int a1=x.s[1].x; int b1=x.s[1].y; int a2=x.s[1].x1; int b2=x.s[1].y1; if(a2==3&&b2==6) return true; return false; } ll get(node x){ ll t1=0; ll t2=0; int i,j; for(i=1;i<=6;i++){ for(j=1;j<=6;j++){ t1=(t1*base%mod1+x.g[i][j])%mod1; t2=(t2*base%mod2+x.g[i][j])%mod2; } } return t1*base+t2; } int bfs(){ int i,j; queue<node> q; tmp.cnt=0; ll hs=get(tmp); m1[hs]++; q.push(tmp); int ans=-1; while(q.size()){ auto x=q.front(); q.pop(); if(check(x)){ ans=x.cnt; break; } for(int sign=1;sign<=mx;sign++){ int a1=x.s[sign].x; int b1=x.s[sign].y; int a2=x.s[sign].x1; int b2=x.s[sign].y1; if(b1==b2){ if(a1-1>=1&&x.g[a1-1][b1]==0){ node ean=x; ean.s[sign].x=a1-1; ean.s[sign].y=b1; ean.s[sign].x1=a2-1; ean.s[sign].y1=b2; ean.g[a1-1][b1]=sign; ean.g[a2][b2]=0; ll hs=get(ean); if(!m1[hs]){ ean.cnt+=1; m1[hs]++; q.push(ean); } } if(a2+1<=6&&x.g[a2+1][b2]==0){ node ean=x; ean.s[sign].x=a1+1; ean.s[sign].y=b1; ean.s[sign].x1=a2+1; ean.s[sign].y1=b2; ean.g[a2+1][b2]=sign; ean.g[a1][b1]=0; ll hs=get(ean); if(!m1[hs]){ ean.cnt+=1; m1[hs]++; q.push(ean); } } } else if(a1==a2){ if(b1-1>=1&&x.g[a1][b1-1]==0){ node ean=x; ean.s[sign].x=a1; ean.s[sign].y=b1-1; ean.s[sign].x1=a2; ean.s[sign].y1=b2-1; ean.g[a1][b1-1]=sign; ean.g[a2][b2]=0; ll hs=get(ean); if(!m1[hs]){ ean.cnt+=1; m1[hs]++; q.push(ean); } } if(b2+1<=6&&x.g[a2][b2+1]==0){ node ean=x; ean.s[sign].x=a1; ean.s[sign].y=b1+1; ean.s[sign].x1=a2; ean.s[sign].y1=b2+1; ean.g[a2][b2+1]=sign; ean.g[a1][b1]=0; ll hs=get(ean); if(!m1[hs]){ ean.cnt+=1; m1[hs]++; q.push(ean); } } } } } if(ans!=-1&&ans<9) return ans+2; return -1; } int main(){ int i,j; for(i=1;i<=6;i++){ for(j=1;j<=6;j++){ cin>>g[i][j]; mx=max(mx,g[i][j]); } } for(i=1;i<=6;i++){ for(j=1;j<=6;j++){ tmp.g[i][j]=g[i][j]; } } for(int sign=1;sign<=mx;sign++){ int flag=0; for(i=1;i<=6;i++){ for(j=1;j<=6;j++){ if(g[i][j]==sign){ if(g[i][j+2]==sign){ tmp.s[sign]={i,j,i,j+2}; flag=1; break; } if(g[i][j+1]==sign){ tmp.s[sign]={i,j,i,j+1}; flag=1; break; } if(g[i+2][j]==sign){ tmp.s[sign]={i,j,i+2,j}; flag=1; break; } if(g[i+1][j]==sign){ tmp.s[sign]={i,j,i+1,j}; flag=1; break; } } } if(flag) break; } } cout<<bfs()<<endl; }
B题 树形dp
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=4e5+10; const int inf=0x3f3f3f3f; ll f[N][3][3]; int h[N],ne[N],e[N],idx; int in[N]; void add(int a,int b){ e[idx]=b,ne[idx]=h[a],h[a]=idx++; } void dfs(int u,int fa){ f[u][1][0]=1,f[u][2][0]=0; if(in[u]==1&&fa!=-1) return ; f[u][0][0]=f[u][0][1]=f[u][2][0]=f[u][2][1]=0; ll g[2]={0,inf}; ll tmp[2][2]={0,inf,inf,inf}; for(int i=h[u];i!=-1;i=ne[i]){ int v=e[i]; if(v==fa) continue; dfs(v,u); ll tmp1=min(f[v][1][0],min(f[v][0][1],f[v][0][0])); g[1]=min(g[1]+tmp1,g[0]+min(f[v][1][0],f[v][0][0])); g[0]+=tmp1; tmp[1][1]=min(tmp[1][1]+tmp1,min(tmp[0][1]+min(f[v][1][0],f[v][0][0]),tmp[1][0]+min(f[v][2][1],f[v][2][0]))); tmp[1][0]=min(tmp[1][0]+tmp1,tmp[0][0]+min(f[v][1][0],f[v][0][0])); tmp[0][1]=min(tmp[0][1]+tmp1,tmp[0][0]+min(f[v][2][1],f[v][2][0])); tmp[0][0]+=tmp1; f[u][1][0]+=min(f[v][1][0],min(f[v][0][0],min(f[v][0][1],min(f[v][2][0],f[v][2][1])))); f[u][2][1]=min(f[u][2][0]+min(f[v][2][1],f[v][2][0]),f[u][2][1]+f[v][0][1]); f[u][2][0]+=f[v][0][1]; } f[u][0][0]=g[1]; f[u][0][1]=tmp[1][1]; } int main(){ ios::sync_with_stdio(false); memset(h,-1,sizeof h); int n; cin>>n; for(int i=1;i<=n;i++){ for(int j=0;j<3;j++){ for(int k=0;k<2;k++) f[i][j][k]=0x3f3f3f3f; } } for(int i=1;i<n;i++){ int a,b; cin>>a>>b; add(a,b); add(b,a); in[a]++; in[b]++; } dfs(1,-1); cout<<min(f[1][1][0],min(f[1][0][0],f[1][0][1]))<<endl; }
C题 签到
D题 签到
E题 构造，尝试构造最长的序列
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e6+10; int main(){ //ios::sync_with_stdio(false); int t; scanf("%d",&t); while(t--){ ll k,l; cin>>k>>l; if(l>=2000){ printf("-1 "); continue; } ll lt=1999; ll op=k/1999+1; ll x=op*1999-k; ll s=x-op; while(s<=0){ op++; x=op*1999-k; s=x-op; } printf("1999 "); for(int i=0;i<1997;i++)printf("0 "); printf("%d ",-s); printf("%d ",x); } }
H 签到
#include<bits/stdc++.h> using namespace std; typedef long long ll; int main(){ ll n; int t; scanf("%d",&t); while(t--){ scanf("%lld",&n); ll a=(n+1ll)*n; cout<<((n+1ll)^a)<<endl; } }
J bitset暴力二进制枚举
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e6+5; priority_queue<int,vector<int>,greater<int>> q; bitset<510> op[20]; int main(){ int t; cin>>t; while(t--){ int n,m; cin>>n>>m; for(int i=1;i<=m;i++){ string s; cin>>s; int j; op[i].reset(); for(j=(int)s.size()-1;j>=0;j--){ int sign=s[j]-'0'; op[i][j]=sign; } } int res=0x3f3f3f3f; for(int i=0;i<(1<<m);i++){ bitset<510> ans; ans.reset(); int tmp=0; for(int j=0;j<m;j++){ if(i>>j&1){ ans|=op[j+1]; tmp++; } } int flag=0; for(int j=0;j<n;j++){ if(ans[j]==0){ flag=1; break; } } if(!flag){ res=min(res,tmp); } } if(res==0x3f3f3f3f) cout<<-1<<endl; else cout<<res<<endl; } }
K 哈夫曼树
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e6+5; priority_queue<int,vector<int>,greater<int>> q; int main(){ int t; cin>>t; while(t--){ int n; cin>>n; int i; while(q.size()) q.pop(); for(i=1;i<=n;i++){ int x; cin>>x; q.push(x); } ll ans=0; while(q.size()){ if(q.size()==1) break; auto x=q.top(); q.pop(); auto y=q.top(); q.pop(); q.push(x+y); ans+=x+y; } cout<<ans<<endl; } }
L 凸包枚举
#include<bits/stdc++.h> #define LL long long using namespace std; const int maxn=5005; const int inf=0x3f3f3f3f; int n; int q[maxn]; struct Point { LL x,y; Point friend operator + (Point a,Point b) { Point tmp; tmp.x=a.x+b.x; tmp.y=a.y+b.y; return tmp; } Point friend operator - (Point a,Point b) { Point tmp; tmp.x=a.x-b.x; tmp.y=a.y-b.y; return tmp; } }p[maxn]; LL cross(Point a,Point b) { return a.x*b.y-a.y*b.x; } LL dist(Point a,Point b) { return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y); } int cmp(Point a,Point b) { Point x=a-p[1]; Point y=b-p[1]; LL s=cross(x,y); return s>0||(s==0&&dist(p[1],a)<=dist(p[1],b)); } LL area(int a,int b,int c) { Point x=p[b]-p[a]; Point y=p[c]-p[a]; return cross(x,y); } LL cal(int a,int b) { LL mx1,mx2,mn1,mn2; mx1=mx2=-1; mn1=mn2=inf; for(int i=1; i<=n; i++) { if(i!=a&&i!=b) { LL s=area(a,b,i); if(s>0) { mx1=max(mx1,s); mn1=min(mn1,s); } else { mx2=max(mx2,-s); mn2=min(mn2,-s); } } } if(mx1==-1) return mx2-mn2; if(mx2==-1) return mx1-mn1; return mx1+mx2; } int main() { int T; scanf("%d",&T); while(T--) { memset(q,0,sizeof q); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%lld%lld",&p[i].x,&p[i].y); } int m=1; for(int i=2;i<=n;i++) { if(p[i].x<p[m].x||(p[i].x==p[m].x&&p[i].y<p[m].y)) m=i; } swap(p[1],p[m]); sort(p+2,p+n+1,cmp); q[0]=1; q[1]=2; int x=1; for(int i=3;i<=n;i++) { while(x>0&&area(q[x-1],q[x],i)<=0) { x--; } q[++x]=i; } /*for(int i=1;i<=x;i++) printf("%d ",q[i]);*/ LL ans=0; for(int i=1;i<=n;i++) { int j=1; while(abs(area(q[i%x],q[(i+1)%x],q[j%x]))<abs(area(q[i%x],q[(i+1)%x],q[(j+1)%x]))) j++; ans=max(ans,cal(q[i%x],q[j%x])); } if(ans%2==0) printf("%lld ",ans/2); else printf("%lld.5 ",ans/2); } return 0; }