A：
题目链接：点击打开链接
Alice's present
#include <cstdio>#include <iostream>#include <cstring>#include <string>#include <map>#include <queue>#include <set>#include <algorithm>using namespace std;int n, m;int a[501000];map<int, int> mp;int main() {while (scanf("%d", &n) != EOF) {for (int i = 1; i <= n; i++)scanf("%d", &a[i]);scanf("%d", &m);int l, r;for (int j = 1; j <= m; j++){scanf("%d%d", &l, &r);int i;mp.clear();for ( i = r; i >= l; i--){mp[a[i]]++;if (mp[a[i]]>1){ printf("%d\n", a[i]); break; }}if (i < l)printf("OK\n");}printf("\n");}}
B：
题目链接：点击打开链接
Bounty hunter
#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>using namespace std;const int N=1e5+9;double a[N],b[N];double dp[N],_dp[N];int main(){int i,j,k,n,m,T;double x,y;while(~scanf("%d%lf%lf",&n,&x,&y)){for(i=1;i<=n;i++)scanf("%lf%lf",a+i,b+i);dp[n+1]=1;_dp[n+1]=0;for(i=n;i>=1;i--){_dp[i]=_dp[i+1]+b[i]*dp[i+1];dp[i]=max(dp[i+1],_dp[i]/a[i]);}printf("%.2lf\n",dp[1]*x+_dp[1]*y);}return 0;}
C：
题目链接：点击打开链接
Cinema in Akiba
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int MAX_N = 100007;int n, m;int bit[MAX_N], a[MAX_N];int sum(int i) {int s = 0;while (i > 0) {s += bit[i];i -= i & -i;}return s;}void add(int i, int x) {while (i <= n) {bit[i] += x;i += i & -i;}}int main() {while (1 == scanf("%d", &n)) {memset(bit, 0, sizeof bit);for (int i = 1; i <= n; ++i)add(i, 1);for (int i = 1; i <= n; ++i) {int v;scanf("%d", &v);int l = 0, r = n;while (l + 1 < r) {int mid = (l + r) >> 1;if (sum(mid) < v) l = mid;else r = mid;}a[i] = r;add(r, -1);}scanf("%d", &m);for (int i = 0; i < m; ++i) {int v;scanf("%d", &v);if (i == 0) printf("%d", a[v]);else printf(" %d", a[v]);}puts("");}return 0;}/*64 1 3 3 1 161 2 3 4 5 6*/
D:
题目链接:点击打开链接
Decode
#include<cstdio>#include <cstring>#include<vector>using namespace std;int n, k, m;vector<int> base;char s[50];void getbase() {vector<int> v;for(int i = n - 1; i >= 0; --i)for(int j = 0; j < base.size(); ++j)if(base[j] & (1 << i)) {int x=base[j];v.push_back(x);for(int k=0;k<base.size();k++) if(base[k]&(1<<i)) base[k]^=x;break;}base=v;}void out(int x) {for(int i=n-1;i>=0;i--) putchar(((1<<i)&x)?49:48);puts("");}bool jud(int x) {int j=0;for(int i=n-1;i>=0&&x;i--) {if((1<<i)&x) {while(j<base.size()&&(!((1<<i)&base[j])||base[j]>=(1<<i+1))) j++;if(j==base.size()) return 0;else x^=base[j++];}}return 1;}int main() {while(scanf("%d%d%d",&n,&k,&m)!=EOF) {base.clear();for(int i=0; i<k; i++) {scanf("%s",s);int x=0;for(int j=0; j<n; j++) x=(x<<1)|(s[j]-48);base.push_back(x);}getbase();for(int i=0;i<m;i++){scanf("%s",s);int ans=0x7fffffff,diff=100;int x=0;for(int j=0;j<n;j++) x=(x<<1)|(s[j]-48);for(int i=0;i<=n;i++)for(int j=i;j<=n;j++)for(int k=j;k<=n;k++) {int dif=(i!=n)+(j!=n)+(k!=n);int tmp=(x^(1<<i)^(1<<j)^(1<<k))&((1<<n)-1);if((dif<diff||(dif==diff&&tmp<ans))&&jud(tmp)) diff=dif,ans=tmp;}if(ans==0x7fffffff) puts("NA");else out(ans);}}return 0;}
E:
题目链接：点击打开链接
Education Manage System
#include <cstdio>#include <cstring>#include <string>#include <vector>#include <algorithm>using namespace std;const int MAX_N = 200007;const int MAX_T = 24 * 60 * 400;const int day[] = {0, 31, 60, 91, 121,152, 182, 213, 244, 274, 305, 335, 366};struct Node {int l, r;double v;Node () {}Node (int _l, int _r, double _v) {l = _l, r = _r, v = _v;}};int n;double dp[MAX_T];vector<Node> a[MAX_T];int Month(string s) {if(s == "Jan") return 1;if(s == "Feb") return 2;if(s == "Mar") return 3;if(s == "Apr") return 4;if(s == "May") return 5;if(s == "Jun") return 6;if(s == "Jul") return 7;if(s == "Aug") return 8;if(s == "Sep") return 9;if(s == "Oct") return 10;if(s == "Nov") return 11;if(s == "Dec") return 12;}int input() {char str[10], str2[10];scanf("%s", str);int d, h, m;scanf("%d%*s", &d);scanf("%d:%d", &h, &m);scanf("%s", str2);if(str2[0] == 'p') h += 12;return m + h * 60 + (d + day[Month(str) - 1]) * 24 * 60;}int main() {while (1 == scanf("%d", &n)) {memset(dp, 0, sizeof dp);int ma = 0;for (int i = 0; i < MAX_T; ++i) a[i].clear();for (int i = 0; i < n; ++i) {int l, r;double v;l = input();r = input();ma = max(r, ma);scanf("%lf", &v);// printf("%d %d %f\n", l, r, v);a[r + 5].push_back(Node(l, r + 5, v));}for (int i = 1; i < MAX_T; ++i) {dp[i] = dp[i - 1];for (int j = 0; j < a[i].size(); ++j) {dp[i] = max(dp[i], dp[a[i][j].l] + a[i][j].v);}}printf("%.1f\n", dp[MAX_T - 1]);}return 0;}
F：
题目链接：点击打开链接
Fruit Ninja
#include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cmath>#include <cstring>#include <set>#include <vector>#include <map>using namespace std ;const int INF = 0x3F3F3F3F;const int MAXN = 1100 ;const int mod = 100000007 ;map<string,int> LOW , HIGH ;int n , m ;char s1[MAXN] , s2[MAXN] , str[MAXN] ;char op[MAXN] , s[MAXN] ;vector<int> l ;int xx = 0,x=0 ;long long result = 0 ;int fact[10000050];int power(int x,int y){int res=1;while (y){if (y&1) res=(long long)res*x%mod;x=(long long)x*x%mod;y>>=1;}return res;}int inv(int x){return power(x,mod-2);}int C(int x , int y){if(x>10000020) while(1);return (long long)fact[x] * inv(fact[x-y]) % mod * inv(fact[y]) % mod ;}void dfs(int pos , int now , bool flag){if (pos == x){if (now > m) return ;if (flag) result -= C(n + m - now - 1 , n - 1) ;else result += C(n + m - now - 1 , n - 1) ;result %= mod ;return ;}dfs(pos + 1 , now + l[pos] , flag ^ 1) ;dfs(pos + 1 , now , flag ) ;}int main(){fact[0] = 1;for (int i = 1 ; i <= 10000030 ; i++) fact[i] = (long long)fact[i-1] * i % mod;while (~scanf("%d",&n) && n>0){scanf("%d",&m);gets(str);x=0;xx=0;bool flag =true;l.clear() ;while(1){if (!gets(str)) break;if (strlen(str) < 2) break;int X;sscanf(str, "%s%s%s%d",s1,s1,s2,&X);if (*s1 == 'l') {l.push_back(X);x++;if(!X) flag=false;}else {m-=X+1;}xx++;}if (!flag){printf("0\n");continue ;}if (m < 0) printf("0\n");else {result = 0 ;dfs(0,0,0) ;printf("%lld\n",(result % mod + mod) % mod) ;}}return 0 ;}
H：
题目链接：点击打开链接
Help Me Escape
算一下最大开门次数，其实增长是一个二次的，所以爆搜就可以了
#include <cstdio>#include <cmath>#include <cstring>#include <algorithm>using namespace std;const int N = 105;const double P = sqrt(5.0);int a[N], n;double dp[20005];double dfs(int f) {if(dp[f] > 0) return dp[f];dp[f] = 0;for(int i = 0; i < n; i ++) {if(f > a[i]) {int num = (int)((P+1)/2.0*a[i]*a[i]);dp[f] += (double)num/n;} else {dp[f] += (1+dfs(f+a[i]))/n;}}return dp[f];}int main() {int f;while (~scanf("%d%d", &n, &f)) {memset(dp, 0, sizeof dp);for(int i = 0; i < n; i ++) {scanf("%d", &a[i]);}printf("%.3f\n", dfs(f));}return 0;}
I：
题目链接：点击打开链接
Information Sharing
#include <cstdio>#include <iostream>#include <cstring>#include <string>#include <map>#include <queue>#include <set>#include <algorithm>template <class T>inline bool rd(T &ret) {char c; int sgn;if (c = getchar(), c == EOF) return 0;while (c != '-' && (c<'0' || c>'9')) c = getchar();sgn = (c == '-') ? -1 : 1;ret = (c == '-') ? 0 : (c - '0');while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0');ret *= sgn;return 1;}template <class T>inline void pt(T x) {if (x <0) {putchar('-');x = -x;}if (x>9) pt(x / 10);putchar(x % 10 + '0');}using namespace std;const int inf = 1e9;const int N = 100010;const int M = -1;int n;map<string, int>mp;set<int>st[N], tmp;set<int>::iterator it;int f[N], top;int find(int x){ if (x == f[x])return x;int y = find(f[x]); for (it = st[x].begin(); it != st[x].end(); it++)st[y].insert(*it);st[x].clear();return f[x] = y;}void Union(int x, int y){int fx = find(x), fy = find(y);if (fx == fy)return;if (fx > fy)swap(fx, fy);for (it = st[fx].begin(); it != st[fx].end(); it++)st[fy].insert(*it);st[fx].clear();f[fx] = fy;}char op[20];string s, t;int num, u;void add(){cin >> s;f[top] = top;st[top].clear();rd(num);while (num--){ rd(u); st[top].insert(u); }mp[s] = top++;}void check(){cin >> s;int x = find(mp[s]);pt((int)st[x].size()); putchar('\n');}int main() {while (~scanf("%d", &n)) {mp.clear();top = 0;int out = false;while (n--){scanf("%s", op);if (op[0] == 'a'){add();}else if (op[0] == 's'){cin >> s; cin >> t;Union(mp[s], mp[t]);}else{check();out = true;}}}return 0;}/*99arr a 3 1 2 3arr b 1 4arr c 1 5arr d 1 6chec asha a bchec bchec asha a dchec achec d99arr a 0arr b 0arr c 1 1c ac csha b cc bsha a bc a3311 Dig The Wells4085 Peach Blossom Spring1970 Ticket to RideZOJ-3613POJ 3123*/
J：
题目链接： 点击打开链接
Just Another Information Sharing Problem
显然每个人的下界是没什么用的，因为可以通过一些和目标点无关的回路来消除，且一定存在这种回路==，所以直接跑最大流即可，目标点所得到的信息由于不受限制，所以直接从源点建边到汇点就好。
#include <cstdio>#include <iostream>#include <cstring>#include <string>#include <map>#include <queue>#include <set>#include <algorithm>template <class T>inline bool rd(T &ret) {char c; int sgn;if (c = getchar(), c == EOF) return 0;while (c != '-' && (c<'0' || c>'9')) c = getchar();sgn = (c == '-') ? -1 : 1;ret = (c == '-') ? 0 : (c - '0');while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0');ret *= sgn;return 1;}template <class T>inline void pt(T x) {if (x <0) {putchar('-');x = -x;}if (x>9) pt(x / 10);putchar(x % 10 + '0');}using namespace std;const int inf = 1e9;const int N = 5000;const int M = 500010;const int INF = ~0u >> 2;template<class T>struct Max_Flow {int n;int Q[N], sign;int head[N], level[N], cur[N], pre[N];int nxt[M], pnt[M], E;T cap[M];void Init(int n) {this->n = n + 1;E = 0;std::fill(head, head + this->n, -1);}//有向rw 就= 0void add(int from, int to, T c, T rw) {pnt[E] = to;cap[E] = c;nxt[E] = head[from];head[from] = E++;pnt[E] = from;cap[E] = rw;nxt[E] = head[to];head[to] = E++;}bool Bfs(int s, int t) {sign = t;std::fill(level, level + n, -1);int *front = Q, *tail = Q;*tail++ = t; level[t] = 0;while (front < tail && level[s] == -1) {int u = *front++;for (int e = head[u]; e != -1; e = nxt[e]) {if (cap[e ^ 1] > 0 && level[pnt[e]] < 0) {level[pnt[e]] = level[u] + 1;*tail++ = pnt[e];}}}return level[s] != -1;}void Push(int t, T &flow) {T mi = INF;int p = pre[t];for (int p = pre[t]; p != -1; p = pre[pnt[p ^ 1]]) {mi = std::min(mi, cap[p]);}for (int p = pre[t]; p != -1; p = pre[pnt[p ^ 1]]) {cap[p] -= mi;if (!cap[p]) {sign = pnt[p ^ 1];}cap[p ^ 1] += mi;}flow += mi;}void Dfs(int u, int t, T &flow) {if (u == t) {Push(t, flow);return;}for (int &e = cur[u]; e != -1; e = nxt[e]) {if (cap[e] > 0 && level[u] - 1 == level[pnt[e]]) {pre[pnt[e]] = e;Dfs(pnt[e], t, flow);if (level[sign] > level[u]) {return;}sign = t;}}}T Dinic(int s, int t) {pre[s] = -1;T flow = 0;while (Bfs(s, t)) {std::copy(head, head + n, cur);Dfs(s, t, flow);}return flow;}};Max_Flow <int>F;int n, m, l[211], r[210];set<int>st[205], tmp;set<int>::iterator it;vector<int>G;void input(){G.clear();for (int i = 1, num, u; i <= n; i++){rd(num);rd(l[i]); rd(r[i]);st[i].clear();while (num--){ rd(u); st[i].insert(u); G.push_back(u); }}sort(G.begin(), G.end());G.erase(unique(G.begin(), G.end()), G.end());rd(m);for (int i = 1; i <= n; i++){tmp.clear();for (it = st[i].begin(); it != st[i].end(); it++)tmp.insert(lower_bound(G.begin(), G.end(), *it) - G.begin() + 1);st[i] = tmp;}}int main() {while (~scanf("%d", &n)) {input();int from = 0, to = n + G.size() + 1;F.Init(to + 10);for (int i = 1; i <= n; i++){F.add(from, i, r[i], 0);for (it = st[i].begin(); it != st[i].end(); it++){F.add(i, n + (*it), 1, 0);}}F.add(from, m, st[m].size(), 0);for (int i = 0; i < G.size(); i++)F.add(n + 1 + i, to, 1, 0);printf("%d\n", F.Dinic(from, to));}return 0;}
K：
题目链接：点击打开链接
Keep Deleting
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;char a[257], b[51];int main() {while (~scanf("%s", a)) {int l = strlen(a);scanf("%s", b);int len = strlen(b), size = l-1, cnt = 0;for(int i = l-1; i < len; i ++) {b[size++] = b[i];if(size >= l) {int ok = 1;for(int j = 0; j < l; j ++) {if(a[j] != b[size-l+j]) {ok = 0;break;}}if(ok) {cnt ++;size -= l;}}}printf("%d\n", cnt);}return 0;}
