1，2题较水，然而我还是打了2个多小时的t2，t3打暴力数组没开够只有20分，（我们班把t3做出来了的是真强）
t1没什么好说的，只是公式难退推（所以我到现在都还没推出来）
注意数据范围，开long long就好
#include<bits/stdc++.h> using namespace std; int main(){ long long a,b; scanf("%lld%lld",&a,&b); long long c=a*b-a-b; printf("%lld",c); return 0; }//简洁明了
t2是真写，虽然思路好像有点问题但测试数据太水没测出来，哈哈
#include<bits/stdc++.h> using namespace std; char cx1[4][1000]; bool bj[1000]; int rea[1000]; int main(){ //freopen("in.txt","r",stdin); int t;scanf("%d",&t); while(t--){ int l;char fzd[10]={0},cx[10]={0}; bool ok=0; stack <int> s;while(!s.empty()) s.pop(); memset(bj,0,sizeof(bj));memset(cx1,0,sizeof(cx1));memset(rea,0,sizeof(rea)); scanf("%d",&l);getchar();scanf("%s",&fzd);getchar(); for(int i=1;i<=l;i++){ scanf("%s",&cx); if(cx[0]=='F'){ s.push(i);getchar(); scanf("%s",&cx);getchar(); if(bj[cx[0]]) ok=1; bj[cx[0]]=1; cx1[2][i]=cx[0]; scanf("%s",&cx);getchar(); if(cx[0]=='n') cx1[0][i]=cx[0]; else if(cx[1]>='0'&&cx[1]<='9'){cx1[0][i]=(cx[0]-'0')*10+cx[1]-'0';} else cx1[0][i]=cx[0]-'0'; scanf("%s",&cx);getchar(); if(cx[0]=='n') cx1[1][i]=cx[0]; else if(cx[1]>='0'&&cx[1]<='9'){cx1[1][i]=(cx[0]-'0')*10+cx[1]-'0';} else cx1[1][i]=cx[0]-'0'; } else if(cx[0]=='E'){ if(s.empty()){ok=1;continue;} int hh=s.top();s.pop();bj[cx1[2][hh]]=0;cx1[0][i]=-1; if(cx1[0][hh]>cx1[1][hh]){ for(int mm=hh+1;mm<=i;mm++) if(cx1[0][mm]==-1) rea[mm]=-1; } else { if(cx1[1][hh]=='n'&&cx1[0][hh]<cx1[1][hh]){ rea[i]='n'+1; } else rea[i]=1; if(cx1[0][i-1]==-1&&rea[i-1]>'n'){ if(rea[i]==1) rea[i]=rea[i-1]; else rea[i]=rea[i-1]+1; } } } } if(!s.empty()) ok=1; if(ok) { printf("ERR ");continue; } int ans=0; for(int i=1;i<=l;i++) ans=max(ans,rea[i]); if(ans==0) ans=1; int aa; if(fzd[2]=='1') aa=1; else { if(fzd[5]>='0'&&fzd[5]<='9') aa=fzd[2]+(fzd[4]-'0')*10+fzd[5]-'0'; else aa=fzd[4]-'0'+fzd[2]; } if(aa==ans) printf("Yes "); else printf("No "); } return 0; }
t3先放一下，正解还没想出来
未完待续。。。
开始t3。。
t3是个动态规划；先用spfa找到最短路，再反向从n点dfs（为什么？因为如果从1点dfs的话很可能会无法到达n，就会进入死胡同，若从n走的话就会优化些（不要问我怎么知道的，我看的题解知道的（逃
关于dfs中维护的状态，用root代表当前点，l指k还剩多少，dp[i][j]指从n到i的距离<最短距离+k的方案数，状态转移的话u->v dis[u]-dis[v]+k-w[u,v](还是有点难理解 )
还有就是要判断0环的话就在dfs的时候加一个数组用来记录当前状态是否走过，如果走过直接返回-1
#include<bits/stdc++.h> #define maxn 100010 #define maxm 200010 using namespace std; inline int read(){ int x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0') {if(ch=='-') ch=getchar();} while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,p,k,head1[maxn],head2[maxn],dis[maxn],dp[maxn][60],size1,size2,working[maxn][60]; struct edge{ int v,w,nex; }e1[maxm],e2[maxm]; void adde1(int u,int v,int w){e1[size1].v=v;e1[size1].w=w;e1[size1].nex=head1[u];head1[u]=size1++;} void adde2(int u,int v,int w){e2[size2].v=v;e2[size2].w=w;e2[size2].nex=head2[u];head2[u]=size2++;} void spfa(){ queue<int> q;q.push(1);dis[1]=0; while(!q.empty()){ int u=q.front();q.pop(); for(int i=head1[u];~i;i=e1[i].nex){ int v=e1[i].v,w=e1[i].w; if(dis[v]>dis[u]+w){ dis[v]=dis[u]+w; q.push(v); } } } } int dfs(int root,int l){ int ans=0; if(l>k||l<0) return 0; if(working[root][l]) { return -1; } if(dp[root][l]!=-1) return dp[root][l]; working[root][l]=true; for(int i=head2[root];~i;i=e2[i].nex){ int v=e2[i].v,w=e2[i].w; int val=dfs(v,dis[root]+l-dis[v]-w); if(val==-1) return -1; ans=(ans+val)%p; } working[root][l]=false; if(root==1&&l==0) ans++; dp[root][l]=ans; return ans; } int work(){ size1=size2=0;memset(head1,-1,sizeof(head1));memset(head2,-1,sizeof(head2));memset(working,0,sizeof(working)); n=read();m=read();k=read();p=read(); for(int i=1;i<=m;i++){ int x=read(),y=read(),z=read(); adde1(x,y,z);adde2(y,x,z); } memset(dis,0x3f3f3f3f,sizeof(dis));memset(dp,-1,sizeof(dp)); spfa(); int ans=0; for(int i=0;i<=k;i++){ int val=dfs(n,i); if(val==-1) return val; ans=(ans+val)%p; } return ans; } int main(){ int t=read(); while(t--){ printf("%d ",work()); } return 0; }//奇丑无比的代码。。
来一波感慨：数据范围要看清，不然成绩吓死你