构造 1002 GTW likes gt
题意：中文题面
分析：照着题解做的，我们可以倒着做，记一下最大值，如果遇到了修改操作，就把最大值减1，然后判断一下这个人会不会被消灭掉，然后再更新一下最大值。不知道其他的做法是怎么样的
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std; #define lson l, mid, o << 1
#define rson mid + 1, r, o << 1 | 1
const int N = 5e4 + 5;
const int INF = 0x3f3f3f3f;
int n, m;
int a[N], b[N], cnt[N], mx[2]; int main(void) {
int T; scanf ("%d", &T);
while (T--) {
scanf ("%d%d", &n, &m);
for (int i=1; i<=n; ++i) {
scanf ("%d%d", &a[i], &b[i]);
}
memset (cnt, 0, sizeof (cnt));
for (int c, i=1; i<=m; ++i) {
scanf ("%d", &c); cnt[c]++;
}
mx[0] = mx[1] = 0; int ans = n;
for (int i=n; i>=1; --i) {
mx[0] -= cnt[i]; mx[1] -= cnt[i];
if (mx[a[i]^1] > b[i]) ans--;
mx[a[i]] = max (mx[a[i]], b[i]);
}
printf ("%d\n", ans);
} return 0;
}
打表+数学 1003 GTW likes function
题意：中文题面
分析：打表才能看出来是 n + x + 1，然后可以直接套模版计算了。严格证明看官方题解。
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std; typedef long long ll; ll euler(ll x) {
ll ret = x, t = x;
for (int i=2; i*i<=x; ++i) {
if (t % i == 0) {
ret = ret / i * (i - 1);
while (t % i == 0) t /= i;
}
}
if (t > 1) ret = ret / t * (t - 1);
return ret;
} ll euler2(ll x) {
ll ret = 1, i = 2;
for (; i*i<=x; ++i) {
if (x % i == 0) {
x /= i;
ret *= (i - 1);
while (x % i == 0) {
x /= i; ret *= i;
}
}
}
if (x > 1) ret *= (x - 1);
return ret;
} ll _pow(ll x, int n) {
ll ret = 1;
for (int i=1; i<=n; ++i) {
ret *= x;
}
return ret;
} ll comb(int n, int m) {
ll ret = 1;
for (int i=1; i<=m; ++i) {
ret = ret * n; n--;
}
ll ret2 = 1, t = m;
for (int i=1; i<=m; ++i) {
ret2 = ret2 * t; t--;
}
return ret / ret2;
} ll fun(int x) {
ll ret = 0;
for (int i=0; i<=x; ++i) {
ret += _pow (-1, i) * _pow (2, 2 * x - 2 * i) * comb (2 * x - i + 1, i);
}
return ret;
} int main(void) {
/*ll f = fun (10);
printf ("i: %d f: %d\n", 0, f);
for (int i=1; i<=10; ++i) {
f = fun (f);
printf ("i: %d f: %d\n", i, f);
}*/
ll n, x;
while (scanf ("%I64d%I64d", &n, &x) == 2) {
printf ("%I64d\n", euler2 (n + x + 1));
} return 0;
}