2021CCPC女生赛

本文主要是介绍2021CCPC女生赛，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

这篇题解题目的顺序是按照我认为的难度顺序来的。

K.音乐游戏

  把每一行的字符串读进来之后，直接去计算这个字符串中有多少个\("-"\)字符就可以了

int n; std::cin >> n;
i64 ans = 0;
rep(i,0,n + 1) { // for (int i = 0; i < n + 1; i ++ ) 读到n + 1的原因是getline读取字符串的时候好像会多读取一个空串进来
	std::string s;
	std::getline(std::cin,s);
	ans += count(all(s), '-');
}
std::cout << ans << "\n";

G.3G网络

  直接看样例的输入和输出可以猜出来，直接输出\(\frac{1}{n}\)就可以了。

int n; std::cin >> n;
std::cout << std::fixed << std::setprecision(20) << 1.0 / n << "\n";

  在输出的时候注意保留小数的位数，cout << 1.0 / n;会wa一发。

D.修建道路

  可能有些人觉得是最小生成树，但是这个题其实就是一个很简单的贪心，我们直接把原序列上相邻的两个点连边就可以了。

int n; std::cin >> n;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; i ++ ) std::cin >> a[i];
i64 ans = 0;
rep(i,1,n) ans += std::max(a[i], a[i + 1]);

std::cout << ans << "\n";

A.公交线路

  我们从因为我们一开始并不能确定是往那边走，所以我们从起点开始，向前向后分别走\(m\)的长度，分别判断在这两种情况中是否坐错了，如果前后扫的时候都没有发现做错，那就输出Unsure。

int n, x, y;
std::cin >> n >> x >> y;
std::vector<int> a(n + 1);
rep(i,1,n + 1) std::cin >> a[i];
int m; std::cin >> m;
std::vector<int> b(m + 1);
rep(i,1,m + 1) std::cin >> b[i];

bool f = true, ff = true;

for (int i = x - 1; i >= x - m; i -- )  {
	if (a[i] != b[x - i]) f = false;
	if (i == 0) break;
}

for (int i = x + 1; i <= x + m; i ++ ) {
	if (a[i] != b[i - x]) ff = false;
}

if (f && ff) std::cout << "Unsure\n";
else {
	if (f) std::cout << (x > y ? "Right\n" : "Wrong\n");
	else if (ff) std::cout << (x > y ? "Wrong\n" : "Right\n");
}

I.驾驶卡丁车

  纯模拟题，注意读题判断细节就好了，一开始小丁车朝向是向上的，而且每一次操作的时候都要旋转\(45^{\circ}\),所以为了操作方便，我们按照顺时针的方式建立方向数组。

int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

每一次向前走\(v\)的长度的距离，在这个路上可能会遇上障碍，所以我们不能直接让小卡车直接过去，要\(for\)循环一点一点的走，每一步都要去判断，如果是斜着走的话两边不可以都是障碍。

int n, m;
std::cin >> n >> m;
std::vector<std::vector<char>> G(n + 1, std::vector<char> (m + 1));
int x = 0, y = 0;
for (int i = 1; i <= n; i ++ ) {
	for (int j = 1; j <= m; j ++ ) {
		std::cin >> G[i][j];
		if (G[i][j] == '*') x = i, y = j;
	}
}

int q; std::cin >> q;
int v = 0;
int cur = 0;
std::string op; std::cin >> op;
rep(i,0,q) {
	if (op[i] == 'U') v ++;
	if (op[i] == 'D') v = std::max(v - 1, 0);
	if (op[i] == 'L') cur = (cur - 1 + 8) % 8;
	if (op[i] == 'R') cur = (cur + 1) % 8;
	int nx, ny;
	bool flag = true;
	rep(xx, 0, v) {
		nx = x + dx[cur], ny = dy[cur] + y;
		if (nx < 1 || nx > n || ny < 1 || ny > m || G[nx][ny] == '#') {
			std::cout << "Crash! " << x << " " << y << "\n";
			v = 0;
			flag = false;
			break;
		}
		if (cur == 1 || cur == 3 || cur == 5 || cur == 7) {
			if (G[x + dx[(cur - 1 + 8) % 8]][y + dy[(cur - 1 + 8) % 8]] == '#' && 
				G[x + dx[(cur + 1) % 8]][y + dy[(cur + 1) % 8]] == '#') {
				std::cout << "Crash! " << x << " " << y << "\n";
				v = 0;
				flag = false;
				break;
			}
		}
		x = nx, y = ny;
	}
	if (flag) std::cout << x << " " << y << "\n";
}

C.连锁商店

  队友写的说是状压\(dp\)，还没补先贴上代码

#include <bits/stdc++.h>

#define ll long long
#define pii pair<ll, ll>;

using namespace std;

const int N = 1e5+9;

int n, m;
int num, mua;
int dp[39][1<<18];
int mp[39][39];
int c[39], w[39];
int ctake[39], ti[39], unti[39];

vector<int> cpany[39];
void floyd_pre(){
    for(int k = 1; k <= n; ++ k)
        for(int i = 1; i <= n; ++ i)
            for(int j = 1; j <= n; ++ j)
                if(i != j) mp[i][j] |= (mp[i][k] & mp[k][j]);
    if(ctake[1])
	dp[1][0] = w[c[1]];
    else{
	dp[1][1<<unti[c[1]]] = w[c[1]];
    }
}

int main() {
    cin >> n >> m;
    for(int i = 1; i <= n; ++ i){
		cin >> c[i];
		cpany[c[i]].push_back(i);
	}	
    for(int i = 1; i <= n; ++ i) cin >> w[i];
    for(int i = 1; i <= m; ++ i){
        int u, v;
		cin >> u >> v;
        mp[u][v] = 1;
    }

    for(int i = 1; i <= n; ++ i){
        if(cpany[i].empty()) continue;
        if(cpany[i].size() == 1) ctake[cpany[i][0]] = 1;
        else {
            ti[num] = i;
            unti[i] = num ++;
        }
    }

    floyd_pre();
    for(int u = 1; u <= n; ++ u){
        for(int st = 0; st < 1 << num; ++ st){
            for(int v = 1; v <= n; ++ v){
                if(!mp[u][v]) continue;
                if(ctake[v]) dp[v][st] = max(dp[v][st], dp[u][st] + w[c[v]]);
                if(!ctake[v])
                    if(!(st >> unti[c[v]] & 1))
                        dp[v][st | (1 << unti[c[v]])] = max(dp[v][st | (1 << unti[c[v]])], dp[u][st] + w[c[v]]);
            }
        }
    }
    for(int i = 1; i <= n; ++ i){
    	mua = 0;
        for(int st = 0; st < (1 << num); ++ st)
			mua = max(mua, dp[i][st]);
        cout << mua << "\n";
    }
}

F.地图压缩

  哈希一遍，然后将二维转化为一维之后，就是\(KMP\)直接找到行与列的最小循环节，最后的答案就是行与列最小循环节的长度的乘积

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn = 2009;
const ll p = 1331;
const ll mod = 998244353;

int n, q;
char mp[maxn][maxn];
ll col[maxn][maxn], row[maxn][maxn];
ll rcol[maxn][maxn], rrow[maxn][maxn];
ll mhuash[maxn];
ll rhuash[maxn];
ll s[maxn];
ll sr[maxn];
int nex[maxn];

int work(int len) {
    for(int i = 2, j = 0; i <= len; ++ i){
        while (j && s[i] != s[j + 1]){
            j = nex[j];
        }
        if(s[i] == s[j + 1]){
            ++ j;
        }
        nex[i] = j;
    }
    return len - nex[len];
}

void pre(){
    mhuash[0] = 1;
    for(int i = 1; i <= n; ++ i)
        mhuash[i] = mhuash[i - 1] * p % mod;
    for(int i = 1; i <= n; ++ i){
        for(int j = 1; j <= n; ++ j){
            row[i][j] = (row[i][j - 1] * p + (mp[i][j] - 'a')) % mod;
            col[j][i] = (col[j][i - 1] * p + (mp[i][j] - 'a')) % mod;
        }
    }
}

int main(){
    std::cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> q;
    for(int i = 1; i <= n; ++ i){
        for(int j = 1; j <= n; ++ j){
            cin >> mp[i][j];
        }
    }
    pre();
    while(q--){
        int x1, x2, y1, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        for(int i = x1; i <= x2; ++ i)
            s[i - x1 + 1] = (row[i][y2] - row[i][y1 - 1] * mhuash[y2 - y1 + 1] % mod + mod) % mod;
        int len = x2 - x1 + 1;
        int ansx = work(len);
        for(int i = y1; i <= y2; ++ i)
            s[i - y1 + 1] = (col[i][x2] - col[i][x1 - 1] * mhuash[x2 - x1 + 1] % mod + mod) % mod;
        len = y2 - y1 + 1;
        int ansy = work(len);
        cout << ansx * ansy << "\n";
    }
}

这篇关于2021CCPC女生赛的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！