2017-2018 ACM-ICPC German Collegiate Programming Contest (GCPC 2017)
| 题号 | A | B | C | D | E | F | G | H | I | J | K | L |
| 状态 | . | . | Ο | Ο | . | Ø | Ο | . | Ο | . | Ο | . |
Ο：当场
Ø：已补
. : 待补
A Drawing Borders
待补。
B Buildings
待补。
C Joyride
Code：kk
Thinking：kk
题意游乐场有n个设施，有m条人行道，游乐设施会花费ti的时间和pi的钱，人行道需要花费t的时间，你需要用最少的钱恰好游玩x的时间，起点是1，终点是1，求最少的钱是多少4，并且1必须经过两次。
这道题做的我心情复杂。。
先说解法吧，其实很简单，$dp[i][t]$表示到第i个节点，已经使用了t的时间的最小花费，那么状态转移方程就是$dp[v][t]=min(do[u][t-tv]$，然后用队列存放状态，跑一个类似dijkstra堆优化的东西，只不过不用优先队列，特别注意1必须经过两次，所以一开始要判断一下一号节点的时间。
是不是很简单呢。。然而为了写的方便，我把每个节点自己和自己都连了一个环，然后这样的边数就变成了3*n,而我链式前向星的结构体只开了两倍，显示wa9，连带着队友一起自闭了，其他好多题可以做的啊啊啊啊啊
#include<bits/stdc++.h> #define clr(a,b) memset(a,b,sizeof(a)) using namespace std; typedef long long ll; const int maxn=2010; const ll inf=0x3f3f3f3f3f3f3f3f; ll dp[maxn][maxn],p[maxn],maxx; bool vis[maxn][maxn]; int n,m,x,t,head[maxn],tot; int tim[maxn]; struct node{ int u,t; }st; struct edge{ int to,Next; ll w; }a[maxn<<1]; inline void addv(int u,int v,int w){ a[++tot].to=v; a[tot].w=w; a[tot].Next=head[u]; head[u]=tot; } void bfs(){ clr(dp,inf); if(tim[1]>=x)return; dp[1][tim[1]]=p[1]; queue<node>q; q.push({1,tim[1]}); // vis[1][tim[1]]=1; while(!q.empty()) { st=q.front(); q.pop(); int u=st.u,ti=st.t; // vis[u][ti]=0; if(st.t>x)continue; for(int i=head[u];i!=-1;i=a[i].Next) { int v=a[i].to; int cotime=a[i].w; if(cotime+ti+tim[v]>x)continue; // printf("dbbug "); if(dp[v][cotime+ti+tim[v]]>dp[u][ti]+p[v]){ dp[v][cotime+ti+tim[v]]=dp[u][ti]+p[v]; // printf("%d %d %d ",u,v,dp[v][cotime+ti+tim[v]]); // if(!vis[v][cotime+ti+tim[v]]){ q.push({v,cotime+ti+tim[v]}); // vis[v][cotime+ti+tim[v]] = 1; // } } } } maxx=min(maxx,dp[1][x]); } void pop() { for(int i=1;i<=101001;i++) for(int j=1;j<=101010;j++) ; } int main(){ while(cin>>x) { clr(head,-1),tot=0; scanf("%d%d%d",&n,&m,&t); for(int i=1;i<=m;i++) { int u,v,w; scanf("%d%d",&u,&v); if(u==v) pop(); addv(u,v,t); addv(v,u,t); } for(int i=1;i<=n;i++) { scanf("%d%lld",&tim[i],&p[i]); addv(i,i,0); } maxx=inf; bfs(); if(maxx==inf)puts("It is a trap."); else printf("%lld ",maxx); } }
D.Pants On Fire
Thinking：zz
Code：zz
题意：先给n个谁比谁菜的关系，然后给m个谁比谁菜的关系，判断这m个关系是正确的、错误的还是不明确的。
题解：按n个关系建图，然后直接bfs暴力判断这m个关系是不是对的。
#include<bits/stdc++.h> #define clr(a,b) memset(a,b,sizeof(a)) using namespace std; typedef long long ll; const int maxn=110010; char c[1010],d[1010],tmp[1010]; unordered_map<string,int>mp; vector<int>ve[1010]; int v[550]; int main() { int n,m,i,j,k,cnt,xx,yy,pos,si,qq,ans; while(~scanf("%d %d",&n,&m)) { for(i = 0;i <= 1000;i++) { ve[i].clear(); } cnt = 1; for(i = 0;i < n;i++) { scanf("%s",c); scanf("%s",tmp); scanf("%s",tmp); scanf("%s",tmp); scanf("%s",d); if(!mp[c]) { mp[c] = cnt++; } if(!mp[d]) { mp[d] = cnt++; } xx = mp[c]; yy = mp[d]; ve[yy].push_back(xx); } for(i = 0;i < m;i++) { scanf("%s",c); scanf("%s",tmp); scanf("%s",tmp); scanf("%s",tmp); scanf("%s",d); xx = mp[c]; yy = mp[d]; if(xx == 0 || yy == 0) { printf("Pants on Fire "); continue; } else { queue<int>q; q.push(yy); memset(v,0,sizeof(v)); v[yy] = 1; qq = 0; //printf("111 "); while(!q.empty()) { //printf("222 "); pos = q.front(); q.pop(); //printf("2222 %d ",pos); si = ve[pos].size(); //printf("22222 "); for(j = 0;j < si;j++) { //printf("333 "); if(!v[ve[pos][j]]) { v[ve[pos][j]] = 1; if(xx == ve[pos][j]) { qq = 1; break; } //printf(" %d ",ve[pos][j]); q.push(ve[pos][j]); } } if(qq) { break; } } //printf("999 "); if(qq) { ans = 1; } else { //printf("111 "); queue<int>qqq; qqq.push(xx); memset(v,0,sizeof(v)); v[xx] = 1; qq = 0; while(!qqq.empty()) { pos = qqq.front(); qqq.pop(); si = ve[pos].size(); for(j = 0;j < si;j++) { if(!v[ve[pos][j]]) { v[ve[pos][j]] = 1; if(yy == ve[pos][j]) { //printf("5555 "); qq = 1; break; } qqq.push(ve[pos][j]); } } if(qq) { break; } } if(qq) { ans = 2; } else { ans = 3; } } } if(ans == 1) { printf("Fact "); } else if(ans == 2) { printf("Alternative Fact "); } else { printf("Pants on Fire "); } } } }