第一题
模拟送分。
#include<cstdio> #include<cstring> #include<cctype> #include<cmath> #include<algorithm> #define ll long long using namespace std; int read() { char c;int s=0,t=1; while(!isdigit(c=getchar()))if(c=='-')t=-1; do{s=s*10+c-'0';}while(isdigit(c=getchar())); return s*t; } /*------------------------------------------------------------*/ const int inf=0x3f3f3f3f,maxn=101000,MOD=1000000007; int n; char s[maxn],ans[maxn],nows[maxn]; int main() { int T; scanf("%d",&T); while(T--){ scanf("%s",s+1); int n=strlen(s+1); int nowstep=0,len=0,tot=0; for(int i=1;i<=n;i++)if(isdigit(s[i])){ if(nowstep==1){nows[++len]=s[i];} else if(nowstep==2){ for(int j=1;j<=s[i]-'0';j++){ for(int k=1;k<=len;k++){ ans[++tot]=nows[k]; } } len=0;nowstep=0; } else if(nowstep==0)ans[++tot]=s[i]; } else{ if(nowstep==0&&s[i]=='(')nowstep=1;else if(nowstep==1&&s[i]==')')nowstep=2; } long long ansnum=0; for(int i=1;i<=tot;i++)ansnum=(ansnum*10+ans[i]-'0')%MOD; printf("%lld ",ansnum); } return 0; }
第二题
数学相关，弃坑。
第三题
题意：一个2*n的网格，再保证步数最少的情况下，求从任意格出发遍历完所有格的方案数，格子八连通。n<=10000,T<=100。
算法：数学+递推DP
第四题
计算几何相关，弃坑。
第五题
题意：定义V-number为从左到看单位数字未出现先递增后递减现象的数字，求0~N中满足条件的数字个数。T<=200,lenth(n)<=100
算法：数位DP
第六题
题意：一个无向图，k个给定点为高点，其余为低点，要求拼成若干个高-低-高的三元组（“-”表示有边直连），三元组之间点不重复，求至多拼成多少个三元组。
n<=30,k<=15,T<=20
算法：状压DP
题解：看数据范围猜算法！
f[x][i]表示加入第x个低点后，高点占领状态为i的最大三元组个数，初始f[0][0]=0，显然x可以滚动。
每次加入一个低点，枚举状态，然后在状态中找到两个高点配起来，或不配状态直传。
配的过程用dfs枚举，复杂度(n-k)*2^k*C(2,k)，极限15*2^15*14*15≈10^8，果然要相信自己啊！
#include<cstdio> #include<cstring> #include<cctype> #include<cmath> #include<algorithm> #define ll long long using namespace std; int read() { char c;int s=0,t=1; while(!isdigit(c=getchar()))if(c=='-')t=-1; do{s=s*10+c-'0';}while(isdigit(c=getchar())); return s*t; } /*------------------------------------------------------------*/ const int inf=0x3f3f3f3f,maxn=40,maxk=80010; int n,f[2][maxk],c,k,m,hi[maxn]; bool map[maxn][maxn],high[maxn]; void dfs(int dep,int now,int pre,int cyc,int x){ if(dep==3){ f[now][c]=max(f[now][c],f[pre][cyc]+1); } else{ for(int i=0;i<=k-1;i++)if(map[x][hi[i+1]]&&!(c&(1<<i))){ c|=(1<<i); dfs(dep+1,now,pre,cyc,x); c^=(1<<i); } } } int main() { int T; scanf("%d",&T); while(T--){ n=read();m=read();k=read(); int u,v; memset(map,0,sizeof(map)); for(int i=1;i<=m;i++){ u=read();v=read(); map[u][v]=map[v][u]=1; } memset(high,0,sizeof(high)); for(int i=1;i<=k;i++){ u=read(); high[u]=1; } int nowk=0; for(int i=1;i<=n;i++)if(high[i])hi[++nowk]=i; k=nowk; memset(f,0,sizeof(f)); int x=1; for(int i=1;i<=n;i++)if(!high[i]){ x=1-x; memset(f[x],0,sizeof(f[x])); for(int j=0;j<(1<<k);j++){ f[x][j]=max(f[x][j],f[1-x][j]); c=j; dfs(1,x,1-x,j,i); } } int ans=0; for(int i=0;i<(1<<k);i++)ans=max(ans,f[x][i]); printf("%d ",ans); } return 0; }
战果：rank 100，naive successful！开心>w<！
