比赛链接：http://hihocoder.com/contest/mstest2016oct
A.分别维护一下当前点之前有多少个奇数，多少个偶数。如果当前点和之前点符号不一样并且之前点存在，可以约掉。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 1001000; 5 int n; 6 int a[maxn]; 7 8 int main() { 9 // freopen("in", "r", stdin); 10 int x; 11 while(~scanf("%d", &n)) { 12 for(int i = 1; i <= n; i++) { 13 scanf("%d", &x); 14 a[i] = (x & 1); 15 } 16 int odd = 0, even = 0; 17 for(int i = 1; i <= n; i++) { 18 if(a[i] % 2 == 0) { 19 if(odd) odd--; 20 else even++; 21 } 22 else { 23 if(even) even--; 24 else odd++; 25 } 26 } 27 printf("%d ", odd + even); 28 } 29 return 0; 30 }
B.简单dp，dp(i)维护字符i在满足条件的情况下能够构成的最长的子序列，从头遍历字符串，再枚举a-z 26个字符作为上一个字符，如果构成的字符串不在字典内，则认为当前字符可以从上一个字符转移过来。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef set<string>::iterator sit; 5 const int maxn = 100100; 6 int n, m; 7 char s[maxn]; 8 char x[5], y[5]; 9 set<string> dic; 10 int dp[256]; 11 12 int main() { 13 // freopen("in", "r", stdin); 14 while(~scanf("%d%s",&n,&s)) { 15 dic.clear(); 16 memset(dp, 0, sizeof(dp)); 17 scanf("%d", &m); 18 for(int i = 0; i < m; i++) { 19 scanf("%s", x); 20 y[0] = x[1]; y[1] = x[0]; y[2] = 0; 21 dic.insert(x); dic.insert(y); 22 } 23 string t; 24 for(int i = 0; i < n; i++) { 25 int tmp = 1; 26 t = ""; t += s[i]; 27 for(int j = 'a'; j <= 'z'; j++) { 28 t += j; 29 if(dic.find(t) == dic.end()) tmp = max(tmp, dp[j] + 1); 30 t.pop_back(); 31 } 32 dp[s[i]] = max(dp[s[i]], tmp); 33 } 34 int ret = 0; 35 for(int i = 'a'; i <= 'z'; i++) ret = max(ret, dp[i]); 36 printf("%d ", n - ret); 37 } 38 return 0; 39 }
C.模拟，用小顶堆维护每一次Office的访问，先给到达时间短的优先，否则按学号排序。从到达大门的时刻开始入堆，用pos数组维护学生i的当前位置，pre维护每一个办公室上一个学生办理的时间，入堆的时候需要把学生当前等待和处理的总时间算上。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 10100; 5 const int maxm = 110; 6 typedef pair<int, int> pii; 7 typedef struct Student { 8 int s, t, p, f; 9 vector<pii> off; 10 }Student; 11 Student stu[maxn]; 12 typedef struct Visit { 13 int s, o, b, t; 14 Visit(){} 15 Visit(int s, int o, int b, int t) : 16 s(s), o(o), b(b), t(t) {} 17 friend bool operator<(const Visit& x, const Visit& y) { 18 if(x.b == y.b) return stu[x.s].s > stu[y.s].s; 19 return x.b > y.b; 20 } 21 }Visit; 22 int n, m, k; 23 priority_queue<Visit> pq; 24 int pos[maxn], pre[maxm]; 25 26 int main() { 27 // freopen("in", "r", stdin); 28 int o, t; 29 while(~scanf("%d%d%d",&n,&m,&k)) { 30 for(int i = 0; i < n; i++) { 31 stu[i].off.clear(); stu[i].f = 0; 32 scanf("%d%d%d",&stu[i].s,&stu[i].t,&stu[i].p); 33 for(int j = 0; j < stu[i].p; j++) { 34 scanf("%d%d",&o,&t); 35 stu[i].off.push_back(pii(o, t)); 36 } 37 } 38 for(int i = 0; i < n; i++) { 39 int o = stu[i].off[0].first; 40 int t = stu[i].off[0].second; 41 pq.push(Visit(i, o, stu[i].t+k, t)); 42 pos[i] = 1; 43 } 44 memset(pre, -1, sizeof(pre)); 45 while(!pq.empty()) { 46 Visit tmp = pq.top(); pq.pop(); 47 int s = tmp.s; 48 tmp.b = max(tmp.b, pre[tmp.o]); 49 int f = tmp.b + tmp.t; 50 pre[tmp.o] = f; 51 if(pos[s] == stu[s].p) stu[s].f = f; 52 else { 53 int o = stu[s].off[pos[s]].first; 54 int t = stu[s].off[pos[s]].second; 55 pq.push(Visit(s, o, f+k, t)); 56 pos[s]++; 57 } 58 } 59 for(int i = 0; i < n; i++) printf("%d ", stu[i].f); 60 } 61 return 0; 62 }
D.细化以后数端点数？？？？