| 题号 | A | B | C | D | E | F | G | H | I | J |
| 状态 | Ø | . | . | Ø | . | Ο | . | Ο | . | . |
题意： 给你长度为n的圈， 每次随机的向左走一步或者向右走一步， 问你最后将所有点走过至少一遍，最后一步停留在m点的概率是多少。（T组样例，每次的概率都要乘以之前的概率）。
dfs模拟这个过程，打一个表，会发现如果m点是0，则概率是0，其他所有点都是1/(n-1)。特判n=1就可以了。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=1000000007; ll qpow(ll a, ll b){ ll ret = 1; for(;b; b>>=1){ if(b&1) ret = ret*a%mod; a = a*a%mod; } return ret; } ll N,M,T,ans; int main(){ ans = 1; scanf("%lld",&T); while (T--){ scanf("%lld%lld",&N,&M); if (N==1){ printf("%lld ",ans); } else { if (M==0) ans=0; else ans=ans*qpow(N-1,mod-2)%mod; printf("%lld ",ans); } } return 0; }
题意：给出n个点的无向图，每个点都有一个权值，要求第k小的团的权值是多少。
思路：将所有单独的点放入优先队列，每次取出堆顶的点，像外扩展，第k次出队的团就是第k小团。
用__int128来记录各种状态。
数据出的很满，不要写成多组数据的方式（不要清空最后的优先队列）
#include<bits/stdc++.h> #define clr(a,b) memset(a,b,sizeof(a)) using namespace std; typedef long long ll; const int maxn=110; struct node{ ll w; int id; __int128 status; friend bool operator<(const node &a,const node &b){ return a.w>b.w; } }; priority_queue<node >q; int n,k; ll val[maxn]; char s[maxn][maxn]; __int128 out[maxn]; int main(){ while(cin>>n>>k){ clr(out,0); for(int i=0;i<n;i++){ scanf("%lld",&val[i]); } for(int i=0;i<n;i++){ scanf("%s",s[i]); for(int j=0;j<n;j++){ int ty=s[i][j]-'0'; out[i]=out[i]+(__int128(ty)<<j); } } for(int i=0;i<n;i++){ q.push({val[i],i,__int128(1)<<i}); } k--; if(k==0){ puts("0"); continue; } ll ans=-1; while(!q.empty()){ node st=q.top(); q.pop(); k--; if(k==0){ ans=st.w; break; } for(int i=st.id+1;i<n;i++){ if((out[i]&st.status)==st.status){ q.push({st.w+val[i],i,st.status|(__int128(1)<<i)}); } } } printf("%lld ",ans); // while(!q.empty())q.pop(); } }
题意，给出2n个人，分成两队，给出两个人如果不在同一队的收益，要求最大收益。
思路：正解似乎是搜索，队友比赛的时候卡过去的。
搜索的方法就是，模拟两个数组，一个点要么放入a，要么放入b，放入的时候，直接累计价值，进行dfs，这样的时间复杂度是C（28,14）*28.
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;++i) #define dep(i,a,b) for(int i=b;i>=a;--i) using namespace std; #define ll long long const int N=35; struct node{ short int a[29]; int w; ll ans=0; }p[20]; int a[N][N],c[N],flag[N],col[N],n; ll ans=0,an=0; ll rd() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } void init() { memset(p[1].a,-1,sizeof(p[1].a)); rep(i,1,n) p[1].a[i]=1; p[1].w=n; rep(i,1,n) { c[i]=i; col[i]=0; } rep(i,1,n) rep(j,n+1,2*n) ans=ans+a[i][j]; p[1].ans=ans; an=ans; } inline ll solve(int x,int id) { ll ans=0; int k=n<<1; rep(i,1,k) { ans=ans+(-a[i][x]+a[i][p[id].w])*p[id].a[i]; } ans=p[id].ans+ans+(a[x][p[id].w]<<1); an=max(an,ans); return ans; } int main() { n=rd(); rep(i,1,2*n) rep(j,1,2*n) a[i][j]=rd(); init(); int pos=n,TIME=0; while(c[1]<=n) { while( c[pos]>=n+pos ) pos--; c[pos]++; rep(j,pos+1,n) c[j]=c[j-1]+1; if(pos<n) { ll x=solve(c[pos],n-pos+1); if(col[pos]==0) { col[pos]=1; memset(p[n-pos+2].a,-1,sizeof(p[n-pos+2].a)); rep(j,1,n) p[n-pos+2].a[c[j]]=1; p[n-pos+2].w=c[pos-1]; p[n-pos+2].ans=x; } rep(j,pos+1,n) col[j]=0; memset(p[1].a,-1,sizeof(p[1].a)); rep(j,1,n) p[1].a[c[j]]=1; p[1].w=c[n]; p[1].ans=x; } else{ ll x=solve(c[pos],1); if(col[pos]==0) { col[pos]=1; memset(p[n-pos+2].a,-1,sizeof(p[n-pos+2].a)); rep(j,1,n) p[n-pos+2].a[c[j]]=1; p[n-pos+2].w=c[pos-1]; p[n-pos+2].ans=x; } } pos=n; } printf("%lld ",an); }
题意：给出01矩阵，1的地方是有东西的，求出第二大的子矩阵面积。
思路：其实就是单调栈处理最大子矩阵，过程中稍微加一点点变化就行了。
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;i++) #define dep(i,a,b) for(int i=b;i>=a;i--) using namespace std; #define ll long long const int N=3e5+5; const int mod = 998244353; int ans=0,ans1=0,n,m,p; char ss[1010]; int a[1010][1010],b[1010],s[1010],w[1010]; int sum(int a, int b) { int s = (a + b); if (s >= mod) s -= mod; return s; } int sub(int a, int b) { int s = a - b; if (s < 0) s += mod; return s; } int mult(int a, int b) { return (1LL * a * b) % mod; } ll rd() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int main() { n=rd();m=rd(); rep(i,1,n) { scanf("%s",ss+1); rep(j,1,m) if(ss[j]!='0') a[i][j]=ss[j]-'0'+a[i-1][j]; else a[i][j]=0; } rep(i,1,n) { rep(j,1,m) { b[j]=a[i][j]; //printf("%d ",b[j]); } b[m+1]=0; int p=0; rep(j,1,m+1) { if(b[j]>s[p]) { s[++p]=b[j],w[p]=1; } else{ int width=0; while(s[p]>b[j]) { width+=w[p]; if(width*s[p]>ans) { //printf("i=%d j=%d %d %d ",i,j,ans1,ans); ans1=max(ans,(width-1)*s[p]); ans=width*s[p]; } else if(width*s[p]>ans1) ans1=max(ans1,width*s[p]); p--; } s[++p]=b[j];w[p]=width+1; } } } printf("%d ",ans1); }