T1
结论题
预计得分100
#include<stdio.h> #include<iostream> using namespace std; typedef long long ll; ll a,b; int main(){ cin>>a>>b; cout<<1ll*a*b-1ll*a-1ll*b; return 0; }
T2
细节题
栈模拟
垃圾细节题，写挂了[吐血]
预计得分50
#include<stdio.h> #include<iostream> #define FOR(i,s,t) for(register int i=s;i<=t;++i) using namespace std; int T,data; int n,tot,f,e,ans,cnt,flag,l,r; char S[2333]; char c; int vis[2333],keep[2333]; struct node{ char c; char name; char l[23]; char r[23]; }q[23333]; inline int read(){ char c;while(c=getchar(),c==' '||c==' ');int data=c-48; while(c=getchar(),c>='0'&&c<='9')data=(data<<1)+(data<<3)+c-48;return data; } int main(){ scanf("%d",&T); die:; while(T--){ tot=0; n=read(); cin>>S; f=0;cnt=ans=0;tot=0; for(register int i='a';i<='z';++i) vis[i]=0; for(register int i=1;S[i]!=' ';++i){ if(S[i]=='1'&&f==0){ tot=0; break; } if(S[i]=='^'){ tot=0; f=1; } if(S[i]>='0'&&S[i]<='9') tot=tot*10+S[i]-48; } e=f=0; scanf(" "); FOR(i,1,n){ scanf("%c ",&q[i].c); if(q[i].c=='F'){ scanf("%c ",&q[i].name); scanf("%s ",q[i].l); scanf("%s ",q[i].r); ++f; } else ++e; scanf(" "); } if(e!=f){ puts("ERR"); continue; } f=0; FOR(i,1,n){ if(q[i].c=='F'){ ++f; keep[f]=i; if(vis[q[i].name]){ puts("ERR"); goto die; } if(q[i].l[0]!='n'&&q[i].r[0]=='n'&&flag==0) ++cnt; if(q[i].l[0]=='n'&&q[i].l[0]!='n') ++flag; if(q[i].l[0]!='n'&&q[i].r[0]!='n'){ l=0;r=0; for(register int j=0;q[i].l[j]!=' ';++j) l=l*10+q[i].l[j]-48; for(register int j=0;q[i].r[j]!=' ';++j) r=r*10+q[i].r[j]-48; if(l>r) ++flag; } ans=max(ans,cnt); vis[q[i].name]=1; } else{ vis[q[keep[f]].name]=0; if(q[keep[f]].l[0]!='n'&&q[keep[f]].r[0]=='n'&&flag==0) --cnt; if(q[keep[f]].l[0]=='n'&&q[keep[f]].r[0]!='n') --flag; if(q[keep[f]].l[0]!='n'&&q[keep[f]].r[0]!='n'){ l=0;r=0; for(register int j=0;q[keep[f]].l[j]!=' ';++j) l=l*10+q[keep[f]].l[j]-48; for(register int j=0;q[keep[f]].r[j]!=' ';++j) r=r*10+q[keep[f]].r[j]-48; if(l>r) --flag; } --f; if(f<0){ puts("ERR"); goto die; } } } ans==tot?puts("Yes"):puts("No"); } return 0; }
T3
DP题
真心不会.
只会k=0的做法
跑最短路，然后由近到远进行转移
剩下的点跑A*，好像RE光了
预计得分30
#include<stdio.h>
#include<iostream>
#include<set>
#include<vector>
#include<queue>
#define FOR(i,s,t) for(register int i=s;i<=t;++i)
#define VIS(now) for(register int e=las[now];e;e=nxt[e])
#define pa pair<int,int>
using namespace std;
typedef long long ll;
priority_queue<pa>heap;
queue<int>q;
const int inf=1<<29;
const int M=400011,N=100011;
int dp[N];
int n,m,k,p,tot,T,ans,f;
int nxt[M],las[N],to[M],w[M],dis[N],vis[N];
int x[M],y[M],z[M];
inline void add(int x,int y,int z){
nxt[++tot]=las[x];las[x]=tot;
to[tot]=y;w[tot]=z;return;
}
inline int read(){
char c;while(c=getchar(),c==' '||c=='
');int data=c-48;
while(c=getchar(),c>='0'&&c<='9')data=(data<<1)+(data<<3)+c-48;return data;
}
inline void DJ(int x){
FOR(i,1,n)dis[i]=inf,vis[i]=0;
dis[x]=0;
heap.push(make_pair(0,x));
int now;
while(!heap.empty()){
now=heap.top().second;
heap.pop();
if(vis[now])continue;
vis[now]=1;
VIS(now)
if(dis[to[e]]>dis[now]+w[e]){
dis[to[e]]=dis[now]+w[e];
heap.push(make_pair(-dis[to[e]],to[e]));
}
}
}
inline void dfs(int now,int sum){
if(sum+dis[now]>dis[1]+k)
return;
if(now==n){
if(sum<=dis[1]+k)
++ans;
ans%=p;
return;
}
VIS(now){
dfs(to[e],sum+w[e]);
}
}
inline void solve0(){
FOR(i,1,m){
x[i]=read();
y[i]=read();
z[i]=read();
add(x[i],y[i],z[i]);
}
DJ(1);
int now;
while(!heap.empty())heap.pop();
FOR(i,1,n)vis[i]=0,dp[i]=0ll;
dp[1]=1ll;
heap.push(make_pair(0,1));
while(!heap.empty()){
now=heap.top().second;
heap.pop();
if(vis[now])continue;
vis[now]=1;
VIS(now)
if(dis[to[e]]==dis[now]+w[e]){
dp[to[e]]+=dp[now];
dp[to[e]]%=p;
heap.push(make_pair(-dis[to[e]],to[e]));
}
}
printf("%d
",dp[n]);
}
int main(){
T=read();
die:;
while(T--){
n=read();m=read();k=read();p=read();
tot=0;
FOR(i,1,n)las[i]=0;
if(k==0){
solve0();
continue;
}
FOR(i,1,m){
x[i]=read();
y[i]=read();
z[i]=read();
add(y[i],x[i],z[i]);
}
DJ(n);
tot=0;
FOR(i,1,n)las[i]=0,vis[i]=0;
FOR(i,1,m)
if(z[i]==0)
add(x[i],y[i],z[i]);
tot=0;
FOR(i,1,n)las[i]=0,vis[i]=0;
FOR(i,1,m)add(x[i],y[i],z[i]);
ans=0;
dfs(1,0);
printf("%d
",ans);
}
return 0;
}
Day1 崩了 100+50+30=180