• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

这道题的解题顺序是按照我认为的难度顺序。

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(所有(s),'-');

}

std:cout ans ' \ n

G.3G网络

直接看样本的输入输出,就能猜到。直接输出\(\frac{1}{n}\)即可。

int n;STD : CIN n;

STD : cout STD : fixed STD :3360 set precision(20)1.0/n ' \ n ';

输出时注意小数位数,cout 1.0/n;会发生的。

D.修建道路

可能有人觉得是最小生成树,但这个问题其实是一个很简单的贪。我们可以只连接原始序列中两个相邻的点。

int n;STD : CIN n;

std:vectorint矢量a(n ^ 1);

for(int I=1;I=n;I)STD : CIN a

i64 ans=0;

rep(i,1,n) ans=std:max(a,a[I 1]);

std:cout ans ' \ n

A.公交线路

我们开始是因为一开始不确定要走哪条路,所以从起点出发,分别向前和向后走了\(m\)的长度,判断这两种情况下是否坐错了位置。如果我们来回扫描时没有发现任何错误,我们将输出不确定。

int n,x,y;

STD : CIN n x y;

std:vectorint矢量a(n ^ 1);

rep(i,1,n 1)STD : CIN a

int m;STD : CIN m;

std:vectorint矢量b(m 1);

rep(i,1,m 1)STD : CIN b

bool f=true,ff=true

for(int I=x-1;I=x-m;我- ) {

如果(a!=b[x-I])f=false;

if(I==0)break;

}

for(int I=x 1;I=x m;i ) {

如果(a!=b[I-x])ff=false;

}

if (f ff) std:cout“不确定\ n”;

否则{

if (f) std:cout (x y?右\n' : '错\ n ');

else if (ff) std:cout (x y?错误\n' : '正确\ 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 };

每走一段\(v\)的距离,这条路上就可能遇到障碍物,所以我们不能让皮卡车直接通过。我们必须一点一点地走,并判断每一步。如果你走对角线,你不能都是两边的障碍。

int n,m;

STD : CIN n m;

STD : vector ST : vector char G(n 1,std:vectorch

ar> (m + 1)); int x = 0, y = 0; for (int i = 1; i <= n; i ++ ) { for (int j = 1; j <= m; j ++ ) { std::cin >> G[j]; if (G[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 == 'U') v ++; if (op == 'D') v = std::max(v - 1, 0); if (op == 'L') cur = (cur - 1 + 8) % 8; if (op == '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";
    }
}
Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now