比赛链接：https://www.bnuoj.com/v3/contest_show.php?cid=9056#info
好惨啊快速做完6个水题以后就在电脑前夯吃屎。。
C. Captcha Cracker
暴力。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 100100; 5 char s[maxn]; 6 7 int main() { 8 //freopen("in.txt","r",stdin); 9 int T; 10 scanf("%d", &T); 11 while(T--) { 12 scanf("%s", s); 13 vector<int> ret; 14 for(int i = 0; s[i]; i++) { 15 if(s[i]=='2'||(s[i]=='t'&&s[i+1]=='w'&&s[i+2]=='o')) ret.push_back(2); 16 else if(s[i]=='0'||(s[i]=='z'&&s[i+1]=='e'&&s[i+2]=='r'&&s[i+3]=='o')) ret.push_back(0); 17 else if(s[i]=='4'||(s[i]=='f'&&s[i+1]=='o'&&s[i+2]=='u'&&s[i+3]=='r')) ret.push_back(4); 18 else if(s[i]=='6'||(s[i]=='s'&&s[i+1]=='i'&&s[i+2]=='x')) ret.push_back(6); 19 else if(s[i]=='9'||(s[i]=='n'&&s[i+1]=='i'&&s[i+2]=='n'&&s[i+3]=='e')) ret.push_back(9); 20 } 21 for(int i = 0; i < ret.size(); i++) { 22 printf("%d",ret[i]); 23 } 24 if(ret.size() != 0) printf(" "); 25 } 26 return 0; 27 }
A. Another Server
相邻两数求和求和最小的。
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 #define ll long long 5 #define fori(i,a,b) for(ll i=a;i<=b;i++) 6 7 const ll maxn=1e5+10; 8 int main () 9 { 10 //freopen("in.txt","r",stdin); 11 int T; 12 while(cin>>T) 13 { 14 fori(kase,1,T) 15 { 16 int n; 17 cin>>n; 18 19 int ans=10000; 20 fori(i,1,n-1) 21 { 22 int a,b; 23 cin>>a>>b; 24 ans=min(ans,a+b); 25 } 26 cout<<ans<<endl; 27 28 } 29 } 30 31 return 0; 32 }
E. Euclidean Geometry
找规律，发现边从小到大排序后面积最大的只可能是pi*b^2+pi*(c-b)^2或pi*a^2+pi*(b-a)^2。
）不对答案好像只能是pi*b^2+pi*(c-b)^2。。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 #define eps 1e-9 5 typedef double lld; 6 lld a[6]; 7 const lld pi = (lld)3.1415926535897932384626433832795; 8 9 int main() { 10 //freopen("in.txt", "r", stdin); 11 int T; 12 scanf("%d", &T); 13 while(T--) { 14 for(int i = 0; i <3; i++) cin >> a[i]; 15 sort(a, a+3); 16 printf("%.11lf ", max(pi*a[1]*a[1]+pi*(a[2]-a[1])*(a[2]-a[1]),pi*a[0]*a[0]+pi*(a[1]-a[0])*(a[1]-a[0]))); 17 } 18 return 0; 19 }
K. Keep In Line
记下每个人入队位置，每次出队的时候拿来判断是不是队首的。位置和人名同时更新。
1 #include <cstdio> 2 #include <algorithm> 3 #include <iostream> 4 #include <vector> 5 #include <map> 6 #include <set> 7 using namespace std; 8 9 const int maxn = 1111; 10 int n; 11 int ret; 12 int cur_peo; 13 char opt[maxn], name[maxn]; 14 vector<string> a, b; 15 set<string> msp; 16 map<string, int> vis; 17 map<int, string> siv; 18 19 int main() { 20 //freopen("in.txt","r",stdin); 21 int T; 22 scanf("%d", &T); 23 while(T--) { 24 scanf("%d", &n); 25 vis.clear(); 26 int ord = 1, val = 0; 27 a.clear(); b.clear(); msp.clear(); siv.clear(); 28 for(int i = 0; i < n; i++) { 29 scanf("%s%s", opt, name); 30 msp.insert(name); 31 if(opt[0]=='i') { 32 siv[ord] = name; 33 vis[name] = ord++; 34 } 35 else { 36 if(siv.begin()->first < vis[name]) { 37 val++; 38 } 39 siv.erase(vis[name]); 40 vis.erase(vis.find(name)); 41 } 42 } 43 printf("%d ", msp.size()-val); 44 } 45 return 0; 46 }
B. Borrow Classroom
答案就是判断abs(depth[lca(b, c)]-depth[b]+depth[lca(b, c)]-depth[c]) + depth[c]和depth[a]的大小。
假如相等的时候要看一下c和a的公共祖先是不是根。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 100100; 5 const int Deg = 20; 6 typedef struct Edge { 7 int to, next; 8 }Edge; 9 10 Edge edge[maxn<<1]; 11 int head[maxn], tot; 12 int depth[maxn]; 13 14 void adde(int u, int v) { 15 edge[tot].to = v; edge[tot].next = head[u]; 16 head[u] = tot++; 17 } 18 void init() { 19 tot = 0; 20 memset(head, -1, sizeof(head)); 21 } 22 23 int fa[maxn][Deg]; 24 int deg[maxn]; 25 bool flag[maxn]; 26 27 28 void bfs(int rt) { 29 queue<int> que; 30 deg[rt] = 0; 31 fa[rt][0] = rt; 32 que.push(rt); 33 while(!que.empty()) { 34 int tmp = que.front(); que.pop(); 35 for(int i = 1; i < Deg; i++) { 36 fa[tmp][i] = fa[fa[tmp][i-1]][i-1]; 37 } 38 for(int i = head[tmp]; ~i; i=edge[i].next) { 39 int v = edge[i].to; 40 if(v == fa[tmp][0]) continue; 41 deg[v] = deg[tmp] + 1; 42 fa[v][0] = tmp; 43 que.push(v); 44 } 45 } 46 } 47 48 int lca(int u, int v) { 49 if(deg[u] > deg[v]) swap(u, v); 50 int hu = deg[u], hv = deg[v]; 51 int tu = u, tv = v; 52 for(int det = hv-hu, i = 0; det; det>>=1,i++) { 53 if(det&1) tv = fa[tv][i]; 54 } 55 if(tu == tv) return tu; 56 for(int i = Deg-1;i>=0;i--) { 57 if(fa[tu][i]==fa[tv][i]) continue; 58 tu = fa[tu][i]; 59 tv = fa[tv][i]; 60 } 61 return fa[tu][0]; 62 } 63 64 void dfs(int u, int d) { 65 depth[u] = d; 66 for(int i = head[u]; ~i; i=edge[i].next) { 67 int v = edge[i].to; 68 if(flag[v]) continue; 69 flag[v] = 1; 70 dfs(v, d+1); 71 } 72 } 73 74 int n, q; 75 76 int main() { 77 //freopen("in.txt","r",stdin); 78 int T; 79 int u, v; 80 int a, b, c; 81 scanf("%d", &T); 82 while(T--) { 83 scanf("%d%d", &n,&q); 84 init(); 85 memset(flag, 0, sizeof(flag)); 86 for(int i = 0; i < n-1; i++) { 87 scanf("%d%d",&u,&v); 88 adde(u, v); adde(v, u); 89 flag[v] = 1; 90 } 91 int rt = 1; 92 bfs(rt); 93 memset(flag, 0, sizeof(flag)); 94 memset(depth, 0, sizeof(depth)); 95 flag[1] = 1; 96 dfs(1, 0); 97 while(q--) { 98 scanf("%d%d%d",&a,&b,&c); 99 int p = lca(b, c); 100 int x = abs(depth[p]-depth[b]+depth[p]-depth[c]) + depth[c]; 101 int y = depth[a]; 102 if(x < y) { 103 printf("NO "); 104 } 105 else if(x == y) { 106 int z = lca(a, c); 107 if(z == 1) printf("NO "); 108 else printf("YES "); 109 } 110 else { 111 printf("YES "); 112 } 113 } 114 } 115 return 0; 116 }
D. Disdain Chain
一开始读错题。。。
这张图要求每两个人之间都有一条有向边，就是竞赛图。。一开始以为可以不要边，于是打表出错。。
后来打表成功，发现了出乎意料的结论。。
鄙视链长度永远是n。。
好像也不是那么地出乎意料。。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 int a[55][55] = { 5 {0}, 6 {0,2}, 7 {0,0,8}, 8 {0,0,0,64}, 9 {0,0,0,0,1024}, 10 {0,0,0,0,0,32768}, 11 {0,0,0,0,0,0,2097152} 12 }; 13 14 int n; 15 int main() { 16 //freopen("in.txt","r",stdin); 17 //freopen("out.txt","w",stdout); 18 int T; 19 scanf("%d", &T); 20 while(T--) { 21 scanf("%d", &n); 22 for(int i = 0; i < n; i++) { 23 printf("%d ", a[n-1][i]); 24 } 25 } 26 return 0; 27 }