IOI周赛28普及组总结

A-String Game

发现规律：操作n次后就会回到原来的字符串。
所以操作次数可以%n，再模拟过程即可。

struct node {
    int id;
    char c;
    bool operator < (const node &A) {return A.id > id;}
} s[100005];

for(ll i = 1; i <= n; ++i) {
    scanf("%c", &s[i].c), s[i].id = i;
    if(x < i) s[i].id -= x;
    else s[i].id = n-(x-i);
}
sort(s+1, s+n+1);

B-Sequence Game

一开始打爆搜，之后家记忆化，再改倒搜即可

#define N 1005
int a[N][N*5], f[N][N];

// 核心代码
int dfs(int k, int p) {
    int *t = a[k], x = 0, y = 0, i;
    if(k > n) return 0;
    if(f[k][p] != -1) return f[k][p];
    i = upper_bound(t+1, t+m+1, p)-t;
    if(i <= m) x = dfs(k+1, t[i])+1;
    y = dfs(k+1, p);
    return f[k][p] = x > y? x : y;
}

// main()
for(int i = 1; i <= n; ++i) {
    for(int j = 1; j <= m; ++j) {
        scanf("%d", &k);
        a[i][j] = ++k;
    }
}
memset(f, -1, sizeof(f));
printf("%d", dfs(1, 0));

C-Simple Game

建反向边，进行图的便利，当一个点得到答案，则它能到达的点答案都可以是它的答案，如果已经有答案，取最小，否则直接填上（因为是从小到大枚举，所以取最小这个步骤可以省略）

int n, m, u, v, head[N], a[N];
struct node {int u, v, next;} e[N];

// 核心代码
void dfs(int id, int k) {
    for(int i = head[id]; i; i = e[i].next)
        if(!a[e[i].v]) // 没填过 
            a[e[i].v] = k, dfs(e[i].v, k);
}

// main()
scanf("%d %d", &n, &m);
for(int i = 1; i <= m; ++i) {
    scanf("%d %d", &v, &u); // 建反向边
    e[i].u = u, e[i].v = v;
    e[i].next = head[u], head[u] = i; 
}
for(int i = 1; i <= n; ++i)
    if(!a[i]) printf("%d ", a[i] = i), dfs(i, i);

D-Sweet Game

从后往前一颗颗吃，不断进行处理，用后缀和存储最优值,每一步都取最优值

int n, k, d[N], f[N];
long long ans;

scanf("%d", &n);
for(int i = 1; i <= n; ++i) scanf("%d", &k), ans += k;
for(int i = 1; i <= n; ++i) scanf("%d", &d[i]);
for(int i = n; i >= 1; --i) f[i] = f[i+1]+d[i]; // 倒序处理
// f[i]表示第i个及第i个以后的糖甜度的变化后缀和 
for(int i = 1; i <= n; ++i) ans += max(f[i+1], d[i]*(n-i));
// 取第i+1个及以后的最优值与第i个的变化取最优值 
printf("%lld", ans);