题目传送：Codeforces Round #304 (Div. 2)
A. Soldier and Bananas
思路：水题，等差数列求个和就好了
AC代码：
#include <cstdio>#include <cstring>#include <string>#include <cstdlib>#include <iostream>#include <algorithm>#include <cmath>#include <queue>#include <stack>#include <vector>#include <map>#include <set>#include <deque>#include <cctype>#define LL long long#define INF 0x7fffffffusing namespace std;int main() {int k, n, w;scanf("%d %d %d", &k, &n, &w);LL sum = w * (w + 1) / 2;sum = sum * k;if(n >= sum) {printf("0\n");}else cout << sum – n << endl;return 0;}
B. Soldier and Badges
思路：用一个标记数组来搞，，当前结点访问过就往后找，不过数组要开大点，6000以上，结果因为这被hack了
AC代码：
#include <cstdio>#include <cstring>#include <string>#include <cstdlib>#include <iostream>#include <algorithm>#include <cmath>#include <queue>#include <stack>#include <vector>#include <map>#include <set>#include <deque>#include <cctype>#define LL long long#define INF 0x7fffffffusing namespace std;int vis[10005];int main() {memset(vis, 0, sizeof(vis));int n;scanf("%d", &n);LL ans = 0;for(int i = 0; i < n; i ++) {int t;scanf("%d", &t);if(!vis[t]) vis[t] = 1;else {int k = t;for(; k < 10005; k ++) {if(!vis[k]) break;}ans += (k – t);vis[k] = 1;}}cout << ans << endl;return 0;}
C. Soldier and Cards
思路：队列模拟一下即可，设置一个度来确定是否有没有人win，当超过这个度后即可默认为死循环了。
AC代码：
#include <cstdio>#include <cstring>#include <string>#include <cstdlib>#include <iostream>#include <algorithm>#include <cmath>#include <queue>#include <stack>#include <vector>#include <map>#include <set>#include <deque>#include <cctype>#define LL long long#define INF 0x7fffffffusing namespace std;int main() {int n;int k1, k2;queue<int> q1, q2;scanf("%d", &n);scanf("%d", &k1);for(int i = 0; i < k1; i ++) {int t;scanf("%d", &t);q1.push(t);}scanf("%d", &k2);for(int i = 0; i < k2; i ++) {int t;scanf("%d", &t);q2.push(t);}int cnt = 0;int flag = 0;while(1) {if(q1.empty()) {flag = 2;break;}if(q2.empty()) {flag = 1;break;}if(cnt >= 500000) break;int t1 = q1.front();q1.pop();int t2 = q2.front();q2.pop();if(t1 > t2) {q1.push(t2);q1.push(t1);}else {q2.push(t1);q2.push(t2);}cnt ++;}if(flag == 1) {printf("%d 1\n", cnt);}else if(flag == 2) {printf("%d 2\n", cnt);}else {printf("-1\n");}return 0;}
D. Soldier and Number Game
思路：题目很委婉，其实就是去求b+1到a区间内的数的因子个数总和，用暴力筛即可，但是很不幸的是用了cout超时了一次，然后我就跪啦。。。。
AC代码：
#include <cstdio>#include <cstring>#include <string>#include <cstdlib>#include <iostream>#include <algorithm>#include <cmath>#include <queue>#include <stack>#include <vector>#include <map>#include <set>#include <deque>#include <cctype>#include <ctime>#define LL long long#define INF 0x7fffffffusing namespace std;const int maxn = 5000005;int a[maxn];int num[maxn];LL sum[maxn];void init() {for(int i = 0; i < maxn; i ++) {a[i] = i;}num[0] = 0;num[1] = 0;for(int i = 2; i < maxn; i ++) {for(int j = i; j < maxn; j += i) {while(a[j] != 1 && a[j] % i == 0) {num[j] ++;a[j] /= i;}}}}int main() {//freopen("in.txt", "r", stdin);init();for(int i = 1; i < maxn; i ++) {sum[i] = sum[i-1] + num[i];}int t;scanf("%d", &t);while(t –) {int a, b;scanf("%d %d", &a, &b);printf("%I64d\n", sum[a] – sum[b]); }//printf("%d\n", clock());return 0;}
有多远，走多远，把足迹连成生命线。
