2024 河南萌新联赛 3

B 正则表达式

签到，四个数字都在 $[1,255]$ 之间即为合法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


#include <bits/stdc++.h>
using namespace std;

bool check(string s) {
    int n = s.size();
    int num = 0, dots = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '.') {
            if (num < 0 || num > 255) return false;
            num = 0;
        } else if (isdigit(s[i])) {
            num = num * 10 + (s[i] - '0');
            if (num > 255) return false;
        } else {
            return false;
        }
    }
    if (num < 0 || num > 255) return false;
    return true;
}

int main() {
    int n;
    cin >> n;
    int cnt = 0;
    for(int i=1;i<=n;i++) {
        string s;
        cin >> s;
        if (check(s)) cnt++;
    }
    cout << cnt << endl;
    return 0;
}

C Circle

找规律，手模两遍发现 $n = 1$，时为 $2$，其他情况都是每次增加 $(2 \cdot (n - 1))$ 个圆，化简关系式得 $S(n) = n^2 - n + 2$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve(){
    int n;
    cin>>n;
    if(n==0)
        cout<<"1 ";
    else 
        cout<<1LL*n*n-n+2<<" ";
}

int main(){
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

J keillempkill学姐の卷积

按题意模拟即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long

int n,m;
int a[25][25],b[25][25],c[25][25];

signed main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)cin>>a[i][j];
    }
    for(int i=0;i<m;i++){
        for(int j=0;j<m;j++)cin>>b[i][j];
    }
    for(int i=0;i<m-n+1;i++){
        for(int j=0;j<m-n+1;j++){
            int now=0;
            for(int x=i;x<n+i;x++){
                for(int y=j;y<n+j;y++)
                    now+=(a[x-i][y-j]*b[x][y]);
            }
            cout<<now<<" ";
        }
        cout<<endl;
    }
}

L SSH

大 STL

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int q, n, m;
unordered_map<string, vector<string>> ips, keys;
unordered_map<string, string> p2p;

int main() {
    cin >> m >> n >> q;
    for (int i = 1; i <= m; i++) {
        string pub, pri;
        cin >> pub >> pri;
        p2p[pri] = pub;
    }
    for (int i = 1; i <= n; i++) {
        string ip;
        int k;
        cin >> ip >> k;
        for (int j = 1; j <= k; j++) {
            string user, pub;
            int t;
            cin >> user >> t;
            ips[ip].push_back(user);
            for (int l = 1; l <= t; l++) {
                cin >> pub;
                keys[user].push_back(pub);
            }
        }
    }
    while (q--) {
        string user, ip, pri;
        cin >> user >> ip >> pri;
        if (find(ips[ip].begin(), ips[ip].end(), user) != ips[ip].end() &&
            find(keys[user].begin(), keys[user].end(), p2p[pri]) != keys[user].end()) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }
}

F 累加器

正解是暴力跑一遍，记录从 $1$ 到 $i$ 的改变次数，询问时用 $pre[r] - pre[l]$ 即可

赛时 eng 在找规律了，可以发现从第 $0$ 位开始，每次改变次数都 $/2$，如果遇到前一位原来为 $1$ 现在为 $0$ 的，就将现在记录的 $now + 1$，最后也可得出答案

赛时代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


#include <bits/stdc++.h>
using namespace std;

void solve(){
    int x,y,xx[32],yy[32];
    cin>>x>>y;
    int t=x+y;
    for(int i=31;i>=0;i--){
        if((x>>i)&1)xx[i]=1;
        else xx[i]=0;
        if((t>>i)&1)yy[i]=1;
        else yy[i]=0;
    }
    int now=y,ans=y;
    for(int i=1;i<32;i++){
        if(xx[i-1]==1&&yy[i-1]==0)now++;
        ans+=(now/2);
//         cout<<now<<" ";
        now/=2;
    }
    cout<<ans<<endl;
}

int main(){
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

I 游戏

两次最短路，一次只可以走通路的，另一次先拿钥匙，再走到终点，比较两次哪个短哪个是答案

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55


#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+7;
#define int long long

struct Node {
    int y, w;
};

vector<vector<Node>> edge(N), edges(N);
int n, m, k, dist[N];
int a, b, c, d;
set<pair<int, int>> q;

int dijkstra(int s, int t, vector<vector<Node>> &edge) {
    q.clear();
    fill(dist, dist + N, LLONG_MAX); 
    dist[s] = 0;
    q.insert({dist[s], s});
    while (!q.empty()) {
        int x = q.begin()->second;
        q.erase(q.begin());
        if (x == t) break; 
        for (auto &i : edge[x]) {
            if (dist[x] + i.w < dist[i.y]) {
                q.erase({dist[i.y], i.y});
                dist[i.y] = dist[x] + i.w;
                q.insert({dist[i.y], i.y});
            }
        }
    }
    return dist[t];
}

signed main() {
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++) {
        cin >> a >> b >> c >> d;
        if (d == 1) {
            edge[a].push_back({b, c});
            edge[b].push_back({a, c});
        }
        edges[a].push_back({b, c});
        edges[b].push_back({a, c});
    }
    int ans = LLONG_MAX, fk = -1;
    fk = dijkstra(1, k, edge);
    if (fk != LLONG_MAX) {
        ans = min(dijkstra(1, n, edge), dijkstra(k, n, edges) + fk);
    } else {
        ans = dijkstra(1, n, edge);
    }
    if (ans == LLONG_MAX) cout << "-1\n";
    else cout << ans << endl;
}

K 暴食之史莱姆

对于一个史莱姆，他在左侧能吃掉的数量，即为左侧第一个比他小的史莱姆能吃的数量，右侧同理。所以他能吃的数量即为左侧能吃的数量加上右侧能吃的数量

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+7;

int n,a[N],f[N];
deque<int>q;

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){
        while(!q.empty()&&q.back()>a[i]) q.pop_back();
        f[i]+=q.size();
        q.push_back(a[i]);
    }
    q.clear();
    for(int i=n;i>0;i--){
        while(!q.empty()&&q.back()>a[i])q.pop_back();
        f[i]+=q.size();
        q.push_back(a[i]);
    }
    for(int i=1;i<=n;i++)cout<<f[i]<<" ";
}

int main(){
    int t=1;
//     cin>>t;
    while(t--)solve();
    return 0;
}

E 区间

线段树

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67


#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;

int a[N];

struct Node{
    int l,r,mx,len;
}tr[N<<2];

void build(int now,int l,int r){
    tr[now]=Node{r-l+1,r-l+1,r-l+1,r-l+1};
    if(l==r)return;
    int mid=(l+r)>>1;
    build((now<<1),l,mid);
    build(((now<<1)|1),mid+1,r);
}

Node update(Node x,Node y){
    if(x.len==0)return y;
    if(y.len==0)return x;
    Node ans;
    ans.len=x.len+y.len;
    int tmp=max(x.mx,y.mx);
    ans.mx=max(x.r+y.l,tmp);
    ans.l=x.l;
    ans.r=y.r;
    if(x.l==x.len)ans.l+=y.l;
    if(y.r==y.len)ans.r+=x.r;
    return ans;
}

void change(int now,int l,int r,int x){
    if(l==r){
        a[l]^=1;
        tr[now].l=tr[now].r=tr[now].mx=a[l]^1;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid)change((now<<1),l,mid,x);
    else change(((now<<1)|1),mid+1,r,x);
    tr[now]=update(tr[(now<<1)],tr[((now<<1)|1)]);
}

Node query(int now,int l,int r,int x,int y){
    if(l>=x&&r<=y)return tr[now];
    int mid=(l+r)>>1;
    Node ans={0,0,0,0};
    if(x<=mid)ans=query((now<<1),l,mid,x,y);
    if(y>mid)ans=update(ans,query(((now<<1)|1),mid+1,r,x,y));
    return ans;
}

int main(){
    int n,q;
    cin>>n>>q;
    build(1,1,n);
    while(q--){
        int op,x,y;
        cin>>op>>x;
        if(op==1)change(1,1,n,x);
        else {
            cin>>y;
            cout<<query(1,1,n,x,y).mx<<endl;
        }
    }
}

H 魔法

用 $dp[x][y][k]$, 记录在 $(x, y)$ 处使用 $k$ 次魔法，最小的权值之和

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve(){
    int n,m,h;
    cin>>n>>m>>h;
    vector a(n + 1, vector(m + 1, 0));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)cin>>a[i][j];
    vector dp(n + 1, vector(m + 1, vector(n + m, 1e16)));
    dp[1][1][0]=a[1][1],dp[1][1][1]=0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (i == 1 && j == 1) continue;
            for (int k = 0; k < n + m; k++) {
                dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k] + a[i][j]);
                dp[i][j][k] = min(dp[i][j][k], dp[i][j - 1][k] + a[i][j]);
                if (k) {
                    dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k - 1]);
                    dp[i][j][k] = min(dp[i][j][k], dp[i][j - 1][k - 1]);
                }
            }
        }
    }
    for(int i=0;i<n+m;i++){
        if(dp[n][m][i]<h){
            cout<<i<<endl;
            return;
        }
    }
}

signed main(){
    int t=1;
//     cin>>t;
    while(t--)solve();
}

G 求值

易想到将 $w$ 和前面的关系式分开看，答案即为关系式和 $w$ 最接近时的答案，可以想到 $A$ $B$ $C$ 三者的顺序其实无所谓，只和他们的大小有关系，假设关系式结果为 $S$，$A < B < C$, 那么 $S$ 最小就是 $A \cdot n$，最大就是 $C \cdot n$，所以我们先固定从选 $n$ 个 $A$ 开始，每次循环中增加 $1$ 个 $B - A$ 的值，这样就在 $O(n)$ 的时间中解决了 $A$ $B$ 的数量，再在每次循环中针对 $C$ 进行选取，如果当前 $(W - S) / (C - B)$ 的值大于 $i$ 那么我们就选 $i$ 个 $C$，否则就选 $(W - S) / (C - B - A)$ 个 $C$ 和 $(W - S) / (C - B) + 1$ 的值进行比较，选最优的

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve(){
    int aa[3],a,b,c,n,w;
    cin>>aa[0]>>aa[1]>>aa[2]>>n>>w;
    sort(aa,aa+3);
    a=aa[0],b=aa[1]-aa[0],c=aa[2]-aa[1];
    
    int ans,res=w-a*n;
    ans=res;
    if(ans<=0){
        cout<<-ans<<endl;
        return;
    }
    
    for(int i=1;i<=n;i++){
        res-=b;
        ans=min(ans,abs(res));
        if(res<=0)break;
        if(c==0)continue;
        int t=res/c;
        if(t>i)ans=min(ans,res-c*i);
        else ans=min(ans,res-c*t);
        if(i>t)ans=min(ans,abs(res-c*(t+1)));
    }
    cout<<ans<<endl;
}

signed main(){
    int t;
    cin>>t;
    while(t--)solve();
}

G 开心消消乐

一个数异或他本身为 $0$，如果相邻的数相同，他们只需要消耗一次，不同的就增加消耗，特例是为 $0$，的不需要消耗

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,last=-1,ans=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        if(x!=last){
            last=x;
            if(x!=0)
                ans++;
        }
    }
    cout<<ans<<endl;
}