CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:wangzai_milk:20200614比赛记录 [2020/06/24 11:17]
zars19 [A.Advertising Strategy]
+++ 2020-2021:teams:wangzai_milk:20200614比赛记录 [2020/06/25 21:21] (当前版本)
wzx27
@@ 行 39: / 行 39: @@
 题解：显然至少要有花费要在最后一天给出，其他钱应该是早花早受益，于是在第一天和最后一天花钱。枚举在第一天花的钱，模拟天数增加直到剩下的人可以一次性花钱补全。
+code:
 <hidden>
-<code>
+<code cpp>
 #include<bits/stdc++.h>
 #define ll long long
@@ 行 81: / 行 83: @@
 </hidden>
 \\
+==== C.Carpet ====
+要将$n(1\le n\le 100000)$个点的树铺在$1000000×20$的坐标平面里，使得边与边无端点之外的重合点。
+题解：树剖，将轻儿子往上放，重儿子往右放。
+code:
+<hidden>
+<code cpp>
+#include<bits/stdc++.h>
+using namespace std;
+const int N=1e5+5;
+int n,head[N],cnt,sz[N];
+int x[N],y[N],tot[25];
+struct Node
+{
+	int nxt,to;
+}Edges[N*2];
+void addedge(int u,int v)
+{
+    Edges[++cnt].nxt=head[u];
+    head[u]=cnt;
+    Edges[cnt].to=v;
+}
+void dfs1(int u,int f)
+{
+    sz[u]=1;
+    for(int i=head[u];~i;i=Edges[i].nxt)
+    {
+        int v=Edges[i].to;
+        if(v==f)continue;
+        dfs1(v,u),sz[u]+=sz[v];
+    }
+}
+void dfs2(int u,int f,int d)
+{
+	y[u]=d,x[u]=++tot[d];
+	int maxv=0,k=0;
+    for(int i=head[u];~i;i=Edges[i].nxt)
+    {
+        int v=Edges[i].to;
+        if(v==f)continue;
+        if(sz[v]>maxv)maxv=sz[v],k=v;
+    }
+    for(int i=head[u];~i;i=Edges[i].nxt)
+    {
+        int v=Edges[i].to;
+        if(v==f||v==k)continue;
+        dfs2(v,u,d+1);
+    }
+	if(k)dfs2(k,u,d);
+}
+int main()
+{
+	memset(head,-1,sizeof(head));
+	scanf("%d",&n);
+	for(int i=1;i<n;i++)
+	{
+		int u,v;
+		scanf("%d%d",&u,&v);
+		addedge(u,v),addedge(v,u);
+	}
+	dfs1(1,0),dfs2(1,0,1);
+	for(int i=1;i<=n;i++)printf("%d %d\n",x[i],y[i]);
+	return 0;
+}
+</code>
+</hidden>
 ==== D. Decoding of Varints ====
@@ 行 133: / 行 205: @@
 </hidden>
 \\
+==== F. Fake or Leak ====
+反正就是大模拟。。码力和英语都好差，写了好多次才过
+<hidden>
+<code cpp>
+#include<bits/stdc++.h>
+#define ll long long
+#define pii_ pair<int,int>
+#define mp_ make_pair
+#define pb push_back
+#define fi first
+#define se second
+#define rep(i,a,b) for(int i=(a);i<=(b);i++)
+#define per(i,a,b) for(int i=(a);i>=(b);i--)
+#define show1(a) cout<<#a<<" = "<<a<<endl
+#define show2(a,b) cout<<#a<<" = "<<a<<"; "<<#b<<" = "<<b<<endl
+using namespace std;
+const ll INF = 1LL<<60;
+const int inf = 1<<30;
+const int maxn = 1005;
+inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
+int n,m,k,a,t;
+int nowTime[maxn],nowSolve[maxn],has[maxn],bestTime[maxn],in[maxn],finalAc[maxn];
+char op;
+string name,laterName[maxn],rn[maxn];
+map<string,int> mp;
+void GG()
+{
+    cout<<"Fake"<<endl;
+    exit(0);
+}
+struct node
+{
+    string name;
+    int solve,time,fac;
+    bool operator <(node e){
+        if(solve!=e.solve) return solve>e.solve;
+        if(time!=e.time) return time<e.time;
+        if(fac!=e.fac) return fac<e.fac;
+        return name<e.name;
+    }
+};
+vector<node> team;
+vector<string> res;
+int main()
+{
+    fastio();
+    cin>>n>>m>>k;
+    rep(j,1,m){
+        cin>>name;
+        mp[name] = j;
+        rn[j] = name;
+        rep(i,1,n){
+            cin>>op>>a>>t;
+            if(op=='+'){
+                nowTime[j] += 20*(a-1)+t;
+                nowSolve[j]++;
+                bestTime[j] += 20*(a-1)+t;
+                finalAc[j] = max(finalAc[j],t);
+            }
+            else bestTime[j] += 20*a+240;
+        }
+    }
+    rep(j,1,k){
+        cin>>laterName[j];
+        name = laterName[j];
+        int ti = 0,so = 0,fac=0;
+        has[mp[name]] = 1;
+        rep(i,1,n){
+            cin>>op>>a>>t;
+            if(op=='+'){
+                ti += 20*(a-1)+t;
+                so++;
+                fac = max(fac,t);
+            }
+        }
+        team.pb((node){name,so,ti,fac});
+    }
+    rep(i,1,m){
+        if(!has[i]){
+            team.pb((node){rn[i],nowSolve[i],nowTime[i],finalAc[i]});
+            if(nowSolve[i]<n) team.pb((node){rn[i],n,bestTime[i],240});
+            else team.pb((node){rn[i],n,bestTime[i],finalAc[i]});
+        }
+    }
+    sort(team.begin(),team.end());
+    int cnt = 0,flag = 0;
+    for(node x:team){
+        if(has[mp[x.name]]) flag = 1;
+        if(flag && cnt<k){
+            if(has[mp[x.name]]) {res.pb(x.name);cnt++;}
+            else {
+                in[mp[x.name]]++;
+                if(in[mp[x.name]]==2) GG();
+            }
+        }
+    }
+    rep(i,1,k){
+        if(res[i-1]!=laterName[i]) GG();
+    }
+    cout<<"Leaked"<<endl;
+    return 0;
+}
+</code>
+</hidden>
+\\
+==== G. God of Winds ====
+一个网格图，每个小正方形的边有个权值。可以任选格子，加入一个顺时针或者逆时针的风，用来改变格子周围四条边的权值。右和下是正方形，题目给定权值，问这样的图是否存在。
+注意到每条边只有两个格子能影响它，假设每个 $(i,j)$ 处的格子有 $x_{i,j}$ 个顺时针方向的风，那么整个图就是个等式的差分约束，对每个变量连边然后 $\text{dfs}$ 一遍，判断会不会有矛盾的点。
+<hidden>
+<code cpp>
+#include<bits/stdc++.h>
+#define ll long long
+#define pii_ pair<int,int>
+#define mp_ make_pair
+#define pb push_back
+#define fi first
+#define se second
+#define rep(i,a,b) for(int i=(a);i<=(b);i++)
+#define per(i,a,b) for(int i=(a);i>=(b);i--)
+#define show1(a) cout<<#a<<" = "<<a<<endl
+#define show2(a,b) cout<<#a<<" = "<<a<<"; "<<#b<<" = "<<b<<endl
+using namespace std;
+const ll INF = 1LL<<60;
+const int inf = 1<<30;
+inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
+const int maxn = 250005;
+int n,m;
+int r[505][505],c[505][505];
+int vis[maxn],head[maxn],tot;
+ll dis[maxn];
+struct edge
+{
+    int u,v,w,nxt;
+}es[maxn<<2];
+void add(int u,int v,int w)
+{
+    es[++tot] = (edge){u,v,w,head[u]};
+    head[u] = tot;
+}
+void dfs(int u)
+{
+    vis[u] = 1;
+    for(int i=head[u];~i;i=es[i].nxt){
+        int v = es[i].v,w = es[i].w;
+        if(!vis[v]){
+            dis[v] = dis[u] + w;
+            dfs(v);
+        }else{
+            if(dis[v]!=dis[u]+w){
+                cout<<"No"<<endl;
+                exit(0);
+            }
+        }
+    }
+}
+int main()
+{
+    fastio();
+    memset(head,-1,sizeof(head));
+    cin>>n>>m;
+    rep(i,0,n-1)rep(j,0,m-1){
+        cin>>r[i][j]>>c[i][j];
+    }
+    rep(i,0,n-1){
+        rep(j,0,m-1){
+            int u = i*m+j,v = (i-1+n)%n*m + j;
+            add(u,v,r[i][j]);add(v,u,-r[i][j]);
+            int x = i*m+j,y = i*m + (j-1+m)%m;
+            add(x,y,-c[i][j]);add(y,x,c[i][j]);
+        }
+    }
+    dfs(0);
+    cout<<"Yes"<<endl;
+    return 0;
+}
+</code>
+</hidden>
+\\
 ==== H. Hilarious Cooking ====
 === 题意 ===

CVBB ACM Team

用户工具

站点工具

页面工具