Chlience

【题解】Codeforces 1105
一场非常难受的比赛赛前zyf:今天有没有人和我一起合作啊litble:我我我(举手翘首以待状Chlience:带我...
扫描右侧二维码阅读全文
21
2019/01

【题解】Codeforces 1105

一场非常难受的比赛

赛前

zyf:今天有没有人和我一起合作啊
litble:我我我(举手翘首以待状
Chlience:带我一个

Yaser,oiervictor:一起打比赛撒

Rayment:(我就静静看着

litble:zyf你不是之前特别反感合作的行为的么?
zyf:我已经不是当初的我了

boshi摔门而入

Chlience:打比赛不?
boshi:打打打
litble:一起不?
boshi:别咯,自己搞喽(ai

Yaser:不想上分,不打算了
oiervictor:我也不想打了

其他人:(ai

开赛

一个个假装合作实则没有任何交流

A. Salem and Sticks

水题,首先想到中位数,但是显然会有反例
数据范围小,直接枚举

听说有人这题被卡了smg

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N], n;
int ans, pos;
int read();
int main() {
    n = read();
    for(int i = 1 ; i <= n ; ++ i)
        a[i] = read();
    ans = INT_MAX;
    for(int i = 1; i <= 100; ++ i) {
        int now = 0;
        for(int j = 1; j <= n; ++ j)
            now += max(abs(a[j] - i) - 1, 0);
        if(now < ans) ans = now, pos = i;
    }
    printf("%d %d\n", pos, ans);
    return 0;
}
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag; 
}

B. Zuhair and Strings

求序列中有多少个长度大于 $k$ 的均由同一个字母组成的不相交子串

数据范围小,对于每个不同字符算下答案取最大值

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int n, k;

char s[N];
int ans[30];
int maxans;
int read();
int main() {
    n = read(); k = read();
    scanf("%s", s);
    for(int i = 0; i < 26; ++ i) {
        int nowlen = 0;
        for(int j = 0; j <n ; ++ j) {
            if(s[j] == i + 'a')
                ++ nowlen;
            else nowlen = 0;
            if(nowlen == k) {
                nowlen = 0;
                ++ ans[i];
                maxans = max(maxans, ans[i]);
            }
        }
    }
    printf("%d\n", maxans);
    return 0;
}
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag; 
}

C. Ayoub and Lost Array

求一个 $n$ 个数的序列,序列的每一位在 $[l,r]$ 内,且序列元素总和为三的倍数
问有多少种不同方案

以为是矩阵快速幂但是并不需要
考虑模三余数的转移即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll N = 200010;
ll n, l, r;
ll z[3];
ll f[N][3];
int read();
int main() {
    n = read(); r = read(); l = read();
    z[0] = l / 3 - (r - 1) / 3;
    if(l >= 1)
        z[1] += (l - 1) / 3 + 1;
    if(r - 1 >= 1)
        z[1] -= (r - 2) / 3 + 1;
    if(l >= 2)
        z[2] += (l - 2) / 3 + 1;
    if(r - 1 >= 2)
        z[2] -= (r - 3) / 3 + 1;
    f[0][0] = 1;
    for(int i = 1; i <= n; ++ i) {
        for(int j = 0; j < 3; ++ j) {
            for(int k = 0; k < 3; ++ k) {
                f[i][j] += f[i - 1][(j - k + 3) % 3] * z[k] % mod;
                if(f[i][j] >= mod) f[i][j] -= mod;
            }
        }
    }
    printf("%lld\n", f[n][0]);
    return 0;
}
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag; 
}

D. Kilani and the Game

给定有障碍物的矩阵和一些初始被不同人占领的格子,每回合根据人编号从小到大进行操作,每次将被自己占领的格子 $s[i]$ 步能走到的(不经过其他人的各自)没有被占领的格子占领,问最后每个人占领多少个格子

坑比题,写了 $DFS$ T成了sb
最后 5min 从 0 开始打了个 $BFS$ 然后就下考了???
结果直接交直接 $A$ 掉了我也是很无奈

#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> P;
stack <P> now[10];
stack <P> o[10];

const int N = 1010;
const int M = 10;

bool vis[N][N];
int master[N][N];
int n, m, p;
int s[10];
int ans[10];
char str[N];
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag; 
}
void bfs(int pos) {
    while(!now[pos].empty()) {
        int x = now[pos].top().first;
        int y = now[pos].top().second;
        now[pos].pop();
        if(x - 1 >= 0 && !vis[x - 1][y]) {
            o[pos].push({x - 1, y});
            vis[x - 1][y] = 1;
            master[x - 1][y] = pos;
        }
        if(x + 1 < n && !vis[x + 1][y]) {
            o[pos].push({x + 1, y});
            vis[x + 1][y] = 1;
            master[x + 1][y] = pos;
        }
        if(y - 1 >= 0 && !vis[x][y - 1]) {
            o[pos].push({x, y - 1});
            vis[x][y - 1] = 1;
            master[x][y - 1] = pos;
        }
        if(y + 1 < m && !vis[x][y + 1]) {
            o[pos].push({x, y + 1});
            vis[x][y + 1] = 1;
            master[x][y + 1] = pos;
        }
    }
    while(!o[pos].empty()) {
        now[pos].push(o[pos].top());
        o[pos].pop();
    }
}
int main() {
    n = read(); m = read(); p = read();
    for(int i = 1; i <= p; ++ i) s[i] = read();
    for(int i = 0; i < n; ++ i) {
        scanf("%s", str);
        for(int j = 0; j < m; ++ j) {
            if(str[j] != '.')
                vis[i][j] = 1;
            if(str[j] >= '0' + 1 && str[j] <= '0' + p) {
                now[str[j] - '0'].push({i, j});
                master[i][j] = str[j] - '0';
            }
        }
    }
    while(1) {
        for(int i = 1; i <= p; ++ i)
            for(int j = 1; j <= s[i] && !now[i].empty(); ++ j)
                bfs(i);
        int flag = 0;
        for(int i = 1; i <= p; ++ i)
            if(!now[i].empty())
                flag = 1;
        if(!flag) break;
    }
    for(int i = 0 ; i < n ; ++ i)
        for(int j = 0 ; j < m ; ++ j)
            ++ ans[master[i][j]];
    for(int i = 1; i <= p; ++ i)
        printf("%d ", ans[i]);
    return 0;
}

E. Helping Hiasat

有 $n$ 个事件:

  1. 给你一次修改个人资料的机会
  2. 某位朋友来访问你

个人资料里每个时刻只能有一个朋友的名字
某个朋友感到满意当且仅当每次来访问时都是他的名字

问怎么操作能使得满意的朋友最多?

显然在两次操作 $1$ 之间的朋友只能选择 $1$ 个,也就是说他们是互斥的
所以转化成最小独立集,在两个操作 $1$ 之间的人不能同时选

因为人数较多,所以分成两半
每一半只考虑当前能选的最多的人

然后对前一半做前缀和,表示如果能选择某些人最多能选多少个
然后对于后一半每个状态检测能选的前一半的状态,更新答案

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
const int M = 50;
const int BIN = 1 << 21;
typedef long long ll;
map <string, int> name;
string Name;
int tot;

ll bin[M], g[M];
int opt[N], n, m, half;
int sum[BIN], num[BIN];

int sta[M], top;
bool vis[M];

int read();
void init();
void getG();
void calPre();
void calAns();
int main() {
    init();
    getG();
    calPre();
    calAns();
    return 0;
}
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
void init() {
    n = read(); m = read();
    for(int i = 1; i <= n; ++ i) {
        opt[i] = read() - 1;
        if(!opt[i]) continue;
        cin >> Name;
        if(!name.count(Name))
            name[Name] = ++ tot;
        opt[i] = name[Name];
    }
}
void getG() {
    bin[0] = 1;
    for(int i = 1; i <= m ; ++ i)
        bin[i] = bin[i - 1] << 1;
    for(int i = 1; i <= n + 1; ++ i) {
        if(!opt[i]) {
            for(int j = 1; j < top; ++ j)
                for(int k = j + 1; k <= top; ++ k) {
                    g[sta[j]] |= bin[sta[k] - 1];
                    g[sta[k]] |= bin[sta[j] - 1];
                }
            while(top) {
                vis[sta[top]] = 0;
                sta[top --] = 0;
            }
        }
        else {
            if(!vis[opt[i]])
                sta[++ top] = opt[i];
            vis[opt[i]] = 1;
        }
    }
}
void calPre() {
    half = m / 2;
    for(int i = 1; i < bin[half]; ++ i) {
        ll cant = 0, first = 0;
        for(int j = 1; j <= half; ++ j)
            if(i & bin[j - 1]) {
                cant |= g[j];
                if(!first) first = j;
            }
        if(cant & i) continue;
        sum[i] = sum[i - bin[first - 1]] + 1;
    }
    for(int i = 1; i < bin[half]; ++ i)
        for(int j = 1; j <= half; ++ j)
            if(i & bin[j - 1])
                sum[i] = max(sum[i], sum[i - bin[j - 1]]);
}
void calAns() {
    int ans = 0;
    for(int i = 1; i < bin[m - half]; ++ i) {
        ll cant = 0, first = 0;
        for(int j = 1; j <= m - half; ++ j)
            if(i & bin[j - 1]) {
                cant |= g[j + half];
                if(!first) first = j;
            }

        ll pre = cant & (bin[half] - 1);
        ll las = cant >> half;
        if(las & i) continue;

        num[i] = num[i - bin[first - 1]] + 1;
        ans = max(ans, num[i] + sum[(bin[half] - 1) - pre]);
    }
    printf("%d\n", ans);
}

赛后

这是我人生中离 rank100 最接近的一次机会
但是因为智障(ai

人生啊
幸好没掉qwq

Orz litble
Orz boshi

Last modification:January 21st, 2019 at 12:15 pm

Leave a Comment