A. Left-handers, Right-handers and Ambidexters
题意：有l个人擅长用左手，有r个人擅长用右手，有a个人可以选择用左手或右手。现在需要构建一个含偶数人的队伍，其中用左手和右手的人数相等，求队伍人数？
思路：简单题
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 using namespace std; 5 int main() 6 { 7 int l, r, a; 8 scanf("%d%d%d", &l, &r, &a); 9 int Min = min(l, r) + a,Max=max(l,r); 10 int ans; 11 if (Min <= Max) ans = 2 * Min; 12 else ans = 2 * Max + 2*((Min - Max) / 2); 13 printf("%d ", ans); 14 return 0; 15 }
B. Intercepted Message
题意：有两条信息，包含相同的文件（大小一样、排列顺序一样），每个文件分成若干包按照顺序在网上传送。已知每个包的大小，求文件可能的最大数目？
思路：从头到尾遍历，当和相同时数目+1
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 const int maxn = 100010; 5 int a[maxn], b[maxn]; 6 int main() 7 { 8 int n, m; 9 scanf("%d%d", &n, &m); 10 for (int i = 0; i < n; i++) scanf("%d", a + i); 11 for (int i = 0; i < m; i++) scanf("%d", b + i); 12 int ans = 0,tmpa=0,tmpb=0,i=0,j=0; 13 while (i <n||j <m) 14 { 15 if (tmpa==tmpb&&tmpa==0) tmpa += a[i++],tmpb+=b[j++] ; 16 else 17 { 18 if (tmpa < tmpb) tmpa += a[i++]; 19 else if (tmpb < tmpa) tmpb += b[j++]; 20 } 21 if (tmpa == tmpb)ans++, tmpa = tmpb = 0; 22 } 23 printf("%d ", ans); 24 return 0; 25 }
C. Zebras
题意：有一个01串，现在问能否分成k个子串（子串中0和1不一定在原串中连续），每个子串以0作为开始和结尾，0和1在串中交替。给出任意一种可行方案。
思路：用vector模拟子串。当当前字符为‘0’时，如果有串为1结尾，0必须放在其后面，否则可以自成新串的开头；如果当前为1，则只能放在0结尾的子串后面
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<vector> 5 using namespace std; 6 const int maxn = 200010; 7 char str[maxn]; 8 int num0=0, num1=0; 9 vector<int>List[maxn]; 10 int main() 11 { 12 scanf("%s", str + 1); 13 int len = strlen(str + 1); 14 for (int i = 1; i <= len; i++) if (str[i] == '0') num0++; 15 num1 = len - num0; 16 if (num1 >= num0 || str[1] == '1'||str[len]=='1') printf("-1 "); 17 else 18 { 19 int curnum = 0,onenum=0;//前者表示List[0]~List[curnum-1]都是以0作为结尾的子串，后者表示List[curnum]~List[curnum+onenum-1]为1作为结尾的子串 20 for (int i = 1; i <= len; i++) 21 { 22 if (str[i] == '0') 23 { 24 List[curnum++].push_back(i); 25 if (onenum) onenum--; 26 } 27 else List[--curnum].push_back(i), onenum++; 28 if (curnum < 0) break; 29 } 30 if (onenum != 0) printf("-1 "); 31 else 32 { 33 printf("%d ", curnum); 34 for (int i = 0; i < curnum; i++) 35 { 36 int sz = List[i].size(); 37 printf("%d", sz); 38 for (int j=0; j < sz; j++) printf(" %d", List[i][j]); 39 printf(" "); 40 } 41 } 42 } 43 return 0; 44 }
D. A Leapfrog in the Array
题意：有n个数，第i个数放在(i+1)/2的位置。每次选取位置最大的数，将其挪至其左侧与其最近的空位置，直至所有数字都在前n个位置。现在有q个询问，问所有操作过后，第qi个位置是哪个数字？
思路：手动模拟一边可知，所有奇数位置不变，所有偶数位置按照+bias,bias/2(init:bias=n-index/2)知道加至bias为奇数为止。
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 typedef long long LL; 5 int main() 6 { 7 LL n; 8 int q; 9 scanf("%I64d%d", &n, &q); 10 for (int i = 1; i <= q; i++) 11 { 12 LL index; 13 scanf("%I64d", &index); 14 if (index % 2 == 1) printf("%I64d ", (index + 1) / 2); 15 else 16 { 17 LL init = n - index / 2; 18 while (init % 2 == 0) index += init, init /= 2; 19 index = (index + init + 1) / 2; 20 printf("%I64d ", index); 21 } 22 } 23 return 0; 24 }
E. Data Center Maintenance
题意：假设一天有h个小时，有一个数据管理中心，有n个数据库，每个数据库每天有一个小时在系统升级当中。有m个人，每个人的数据会有两个备份存放在不同的数据库当中，保证每个人随时都能查到自己的数据。现在需要把若干个数据库的升级时间推后一小时，问其最小为多少？并给出是哪些数据库
思路：如果一个人其数据的其中一个备份所在的数据库U(i,1)推迟一小时后的升级时间刚好和另一个备份所在的数据库U(i,2)的原本的升级时间相同，那么说明要么前一个数据库不升级，要么两个数据库都升级，我们从U(i,1)连一条有向边到U(i,2)，表示U(i,1)升级会影响到U(i,2)。那么我们最后求出这个有向图的所有的强联通分量（当升级处于一个强联通分量中的某一个数据库升级，该强联通分量内所有的数据库都必须升级）。这些强联通分量不能有连出去的边（否则连出去的边所连向的点的所在的数据库也要升级）。我们找到一个数目最小的即可。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<algorithm> 5 #include<cstring> 6 using namespace std; 7 struct edge 8 { 9 int to, next; 10 edge(int tt=0,int nn=0):to(tt),next(nn){} 11 }; 12 const int maxm = 200010; 13 const int maxn = 100010; 14 edge Edge[maxm]; 15 int Head[maxn]; 16 bool isinstack[maxn];//标记是否在搜索栈中 17 int Stack[maxn];//模拟栈，搜索 18 int Belong[maxn];//各结点属于哪一个强联通分量 19 int Cnt[maxn];//各强联通分量节点数 20 int DFN[maxn];//结点u第一次搜索到的序号（时间戳） 21 int Low[maxn];////u或u的子树能够追溯到的最早的栈中节点的序号(时间戳) 22 int n,m,index,top;//节点数,边数，序号,栈顶 23 int totedge;//边数 24 int Bcnt;//强联通分量数 25 26 void Init() 27 { 28 memset(Head, -1, sizeof(Head)); 29 totedge = 0; 30 index = 0; 31 top = -1; 32 memset(DFN, 0, sizeof(DFN)); 33 memset(Low, 0, sizeof(Low)); 34 memset(Cnt, 0, sizeof(Cnt)); 35 } 36 void addedge(int from, int to) 37 { 38 Edge[totedge] = edge(to, Head[from]); 39 Head[from] = totedge++; 40 } 41 void Tarjan(int u) 42 { 43 DFN[u] = Low[u] = ++index; 44 isinstack[u] = true; 45 Stack[++top] = u; 46 for (int i = Head[u]; i != -1; i = Edge[i].next) 47 { 48 int v = Edge[i].to; 49 if (!DFN[v]) 50 { 51 Tarjan(v); 52 if (Low[v] < Low[u]) Low[u] = Low[v]; 53 } 54 else 55 { 56 if (isinstack[v] && DFN[v] < Low[u]) Low[u] = DFN[v]; 57 } 58 } 59 if (DFN[u] == Low[u]) 60 { 61 Bcnt++; 62 int j; 63 do 64 { 65 j = Stack[top--]; 66 isinstack[j] = false; 67 Belong[j] = Bcnt; 68 Cnt[Bcnt]++; 69 } while (j != u); 70 } 71 } 72 void Solve() 73 { 74 for (int i = 1; i <= n; i++) 75 {//结点从1开始编号 76 if (!DFN[i]) Tarjan(i); 77 } 78 int num_1 = 0; 79 for (int i = 1; i <= n; i++) if (Belong[i] == 1) num_1++; 80 //for (int i = 1; i <= n; i++) printf("%d ", Belong[i]); 81 //选择一个强连通分量，要求没有指向其他分量的边(如果有，说明会影响其他data，不符合题意) 82 bool ok[maxn]; 83 memset(ok, 0, sizeof(ok)); 84 for (int i = 1; i <= n; i++) 85 { 86 for (int j = Head[i]; j != -1; j = Edge[j].next) 87 { 88 if (Belong[Edge[j].to] != Belong[i]) ok[Belong[i]] = 1; 89 } 90 } 91 int mincnt = -1,id=-1; 92 for (int i = 1; i <= Bcnt; i++) 93 { 94 if (!ok[i]) 95 { 96 if (mincnt==-1) id = i, mincnt = Cnt[i]; 97 else if (Cnt[i] < mincnt) mincnt = Cnt[i], id = i; 98 } 99 } 100 printf("%d ", mincnt); 101 for (int i = 1; i <= n; i++) 102 { 103 if (Belong[i] == id) 104 { 105 mincnt--; 106 if (mincnt == 0) printf("%d ", i); 107 else printf("%d ", i); 108 } 109 } 110 } 111 112 int U[maxn]; 113 int main() 114 { 115 int M, H; 116 scanf("%d%d%d", &n, &M,&H); 117 Init(); 118 for (int i = 1; i <= n; i++) 119 { 120 scanf("%d", U + i); 121 } 122 123 for (int i = 0; i < M; i++) 124 { 125 int u1, u2; 126 scanf("%d%d", &u1, &u2); 127 if ((U[u1] + 1) % H == U[u2]) addedge(u1, u2); 128 if ((U[u2] + 1) % H == U[u1]) addedge(u2, u1); 129 } 130 Solve(); 131 return 0; 132 }