华水2025校赛复盘分析

前言

在3月29日,我们学校举办了acm校赛,也是我们新生第一次与学长们同台竞技,可是在这次校赛中我并没有打好,一方面因为部分知识点没有学到,另一方面也在于我这一段时间刷题量减少了.到结束我也只ac了6道题,所以在结束后便写了此复盘,所有题中除了两道要用到线段树的问题其他目前都已解决,线段树现在看来实在是复杂,等以后再慢慢来学.

acm

A.谁是老二

题目描述

LilaS 有三个兄弟，分别叫 A、B 和 C。他们之间的年龄关系可以用三个字符 $S_{AB}$,$S_{AC}$,$S_{BC}$ 表示，其含义如下：

如果 $S_{AB}$ 是 < ，那么 A 比 B 年轻；如果是 > ，则 A 比 B 年长。
如果 $S_{AC}$ 是 < ，那么 A 比 C 年轻；如果是 > ，则 A 比 C 年长。
如果 $S_{BC}$ 是 < ，那么 B 比 C 年轻；如果是 > ，则 B 比 C 年长。

LilaS 是个笨蛋，想知道谁是三人中的老二。

输入格式

输入格式如下，其中同一行的每个符号间用空格隔开。

$S_{AB}$ $S_{AC}$ $S_{BC}$

$S_{AB}$,$S_{AC}$,$S_{BC}$ 取值为 < 或 >。
输入不包含矛盾，一定能判断出谁是老二。

输出格式

输出老二的名字 A 或 B 或 C (注意大写)。

样例

样例输入 1

1

< < <

样例输出 1

1

B

由于 A 比 B 年轻， B 比 C 年轻，我们可以确定 C 是老大， B 是老二， A 是老三。因此答案是B。

代码长度限制:16 KB

时间限制:500 ms

内存限制:64 MB

栈限制:8192 KB

answer

这一题并不难,第一眼看到时候想到的是特判但是太麻烦了,后来想到了可以通过建立一个关系表再通过sort进行排序输出中间的一个就行.

 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


#include <bits/stdc++.h>
#define endl "\n"
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    vector<vector<int>> mp(3,vector<int> (3,0));
    vector<char> qu{'A','B','C'};
    char ch;
    cin>>ch;
    if(ch=='>'){
        mp[0][1]=1;
        mp[1][0]=0;
    }else{
        mp[0][1]=0;
        mp[1][0]=1;
    }
    cin>>ch;
    if(ch=='>'){
        mp[0][2]=1;
        mp[2][0]=0;
    }else{
        mp[0][2]=0;
        mp[2][0]=1;
    }
    cin>>ch;
    if(ch=='>'){
        mp[1][2]=1;
        mp[2][1]=0;
    }else{
        mp[1][2]=0;
        mp[2][1]=1;
    }
    sort(qu.begin(),qu.end(),[mp](char a,char b)-> bool{
        return mp[a-'A'][b-'A'];
    });
    cout<<qu[1];
    return 0;
}

B.MieMieMie

题目描述

羊历 998244353 年。

灰太狼为了抓到羊，与众狼假扮成羊混入羊村。聪明的村长察觉到了不对劲，它怀疑羊村可能混进了许多披着羊皮的狼。

一只小羊的叫声是Mie，而一只披着羊皮的狼的叫声是MIE，请你来数一数一共有多少只羊和多少只披着羊皮的狼。

输入格式:

第一行输入一个整数 T (1≤T≤$10^4$)，表示用例组数；

每组测试数据第一行一个整数 n (1≤n≤$2×10^5$)，表示字符串的长度；

每组测试数据第二行一个由大小写英文字母组成的字符串 S，保证字符串的长度 len(S)=n；

题目保证每组测试用例的 n 的和不超过 2×$10^5$。

输出格式:

输出共 T 行，每行两个整数，分别表示羊的数量和披着羊皮的狼的数量。

样例:

Example Input:

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


6
1
M
2
Mi
3
Mie
6
MIEMie
9
MieMieMie
12
mIEmIemieMIe

Example Output:

代码长度限制:16 KB

时间限制:1000 ms

内存限制:512 MB

栈限制:8192 KB

answer

这一题倒也不是难题,直接通过find分别进行查找记录数量就行,不过比赛时一开始我stl用的不熟并没有这么想,没仔细看输入样例,而用的for循环3个一对查找的而吃了一次wa.

 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>
#define endl "\n"
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin>>t;
    while(t--){
        int n;
        string s;
        cin>>n>>s;
        int ans1=0,ans2=0;
        int i=s.find("Mie");
        while(i!=string::npos){
            i=s.find("Mie",i+3);
            ans1++;
        }
        i=s.find("MIE");
        while(i!=string::npos){
            i=s.find("MIE",i+3);
            ans2++;
        }
        cout<<ans1<<" "<<ans2<<endl;
    }
    return 0;
}

C.LilaS 的颜色树

题目描述

LilaS 种了一棵颜色树，树上有 N 个顶点，编号为 1 ~ N 。第 i 条边连接顶点 $A_i$ 和 $B_i$。顶点 i 被涂上了颜色 $C_i$ （颜色用正整数表示）。

现在，LilaS 想修剪一下这颗颜色树，于是他便按照下面的规则挑选出好的顶点：

从顶点 1 到顶点 x 的最短路径中，除了顶点 x 本身之外，不包含与顶点 x 颜色相同的顶点时，顶点 x 被认为是好的。

LilaS 想知道按照上面规则，有哪些顶点是好顶

点。

输入格式

输入格式如下，其中同一行的每个符号间用空格隔开：

N $C_1$ … $C_N$ $A_1$ $B_1$ ⋮ $A_N$−1 $B_N$−1

2≤N≤$10^5$
1≤$C_i$≤$10^5$
1≤$A_i$,$B_i$≤N
给定图形是一棵树。
输入值均为整数。

输出格式

每一行输出一个整数，按升序输出所有好顶点。

样例

样例输入 1

1
2
3
4
5
6
7


6
2 7 1 8 2 8
1 2
3 6
3 2
4 3
2 5

样例输出 1

例如，从顶点 1 到顶点 6 的最短路径包含顶点 1,2,3,6 。其中只有顶点 6 本身与顶点 6 涂上了相同的颜色，因此它是一个好顶点。
另一方面，从顶点 1 到顶点 5 的最短路径包含顶点 1,2,5 ，而顶点 1 与顶点 5 被涂上了相同的颜色，因此顶点 5 不是一个好顶点。

样例输入 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


10
3 1 4 1 5 9 2 6 5 3
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10

样例输出 2

代码长度限制:16 KB

时间限制:1000 ms

内存限制:1024 MB

栈限制:8192 KB

answer

这一题是一道和树相关的dfs遍历的题,dfs遍历时记下当前节点的颜色,回溯时减一即可,并且每次dfs判断其之前节点颜色数量是否为0,即可判断其好坏,由于比赛是的我并未了解太多的数据结构与算法,我们也还未开课,我当时缺乏对dfs和树相关的练习,所以当时这一题也就没做出来,下来后学习了相关的知识才解决这道题,

 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


#include <bits/stdc++.h>
#define rep(i,a,b) for(ll i=a; i<=b; i++)
#define endl "\n"
//#define MOD 
using namespace std;
using vll = vector<long long>;
using ll = long long;
using ull = unsigned long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    ll n;
    ll maxclr=0;
    cin>>n;
    vll clr(n+1);
    vector<vll> jz(n+1);
    vector<bool> ans(n+1,0);
    rep(i,1,n){
        cin>>clr[i];
        maxclr=max(clr[i],maxclr);
    }
    vll cnum(maxclr+1,0);
    rep(i,0,n-2){
        ll a,b;
        cin>>a>>b;
        jz[a].push_back(b);
        jz[b].push_back(a);
    }
    auto dfs = [&ans,&jz,&cnum,&clr](auto dfs,ll a,ll b) -> void {
        if(!cnum[clr[a]]) ans[a]=1;
        cnum[clr[a]]++;
        for(auto i: jz[a]){
            if(i==b) continue;
            dfs(dfs,i,a);
            cnum[clr[i]]--;
        }
    };
    dfs(dfs,1,0);
    rep(i,0,n){
        if(ans[i]){
            cout<<i<<endl;
        }
    }
    return 0;
}

D.RainbowDash 的旅行

题目描述

湖中心有一座湖心岛，而湖的外围有 m 间木屋，RainbowDash 计划进行一次长达 n 天的旅行。

对于每一天的日程，RainbowDash 都要从当前所在的木屋走到小岛游玩，再走到任何一间木屋（包括出发时所在的木屋）。每间木屋和小岛之间都有若干座桥，其中第 i (i=1,2,3,…,m) 间木屋和小岛有 $a_i$ 座 A 类桥，$b_i$ 座 B 类桥连接。A 类桥提供了车辆，可以更快通过，而 B 类桥只能徒步行走，速度稍慢。由于一天的时间很短，RainbowDash 不想浪费很多时间在赶路，于是他一天通过的两座桥必须至少有一座是 A 类桥。

RainbowDash 当前在 1 号木屋，请问他旅行了 n 天之后，能有多少种不同的路线组合？

输入格式:

第一行输入两个整数 n,m (1≤n≤1000，1≤m≤100)，分别表示旅行的天数，木屋的数量；

第二行输入 m 个整数 $a_1$,$a_2$,$a_3$,…,$a_m$ (0≤$a_i$≤$10^4$)，表示第 i 间木屋和小岛有 $a_i$ 座 A 类桥连接；

第三行输入 m 个整数 $b_1$,$b_2$,$b_3$,…,$b_m$ (0≤$b_i$≤$10^4$)，表示第 i 间木屋和小岛有 $b_i$ 座 B 类桥连接。

输出格式:

输出一个整数，表示旅行 n 天的不同的路线组合数量。

由于答案可能会很大，你只需要输出最终答案对 998244353 取模后的结果即可。

样例

输入样例1:

输出样例1:

1

18

输入样例2:

输出样例2:

1

0

代码长度限制:16 KB

时间限制:1000 ms

内存限制:128 MB

栈限制:8192 KB

answer

这一题是一道动态规划的题目,首先用f[i][j]表示从小屋i到达小屋一共有多少种方案,如果小屋i走a类桥那吗小屋j随意,如果小屋i走b类桥那么小屋j需要走a类桥,则f[i][j]=a[i]*(a[j]+b[j])+b[i]*a[j].

用dp[i][j]表示第i天到达小屋j有多少种方案,dp[i][j]则为所有第i-1天所有小屋到达小屋j的方案和(初始dp[0][1]=1,其他均为0).

答案即为遍历n天到达所有小屋的方案数之和;

 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


#include <bits/stdc++.h>
#define rep(i,a,b) for(ll i=a; i<=b; i++)
#define endl "\n"
#define MOD 998244353
using namespace std;
using vll = vector<long long>;
using ll = long long;
using ull = unsigned long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    ll n,m;
    cin>>n>>m;
    vll a(m+1),b(m+1);
    rep(i,1,m) cin>>a[i];
    rep(i,1,m) cin>>b[i];
    vector<vll> f(m+1,vll (m+1,0)),dp(n+1,vll (m+1,0));
    rep(i,1,m){
        rep(j,1,m){
            f[i][j]=a[i]%MOD*((a[j]%MOD+b[j]%MOD))%MOD%MOD+b[i]%MOD*a[j]%MOD;
        }
    }
    dp[0][1]=1;
    rep(i,1,n){
        rep(j,1,m){
            rep(k,1,m){
                dp[i][j]+=(dp[i-1][k]%MOD*f[k][j]%MOD)%MOD;
                dp[i][j]%=MOD;
            }
        }
    }
    ll ans=0;
    rep(i,1,m){
        ans+=dp[n][i]%MOD;
        ans%=MOD;
    }
    cout<<ans;
    return 0;
}

E.简单路径计数

题目描述

给你一个简单的无向图，图中有 N 个顶点，编号为 1 ~ N ，有 M 条边，编号为 1 ~ M 。边 i 连接顶点 $u_i$ 和顶点 $v_i$ 。每个顶点的度数最多为 10 。

设 K 为从顶点 1 出发的简单路径（无重复顶点的路径）的数目。打印 min(K,$10^6$) .

输入格式

输入格式如下，其中同一行的每个符号间用空格隔开：

N M *$u_1$* *$v_1$* *$u_2$* *$v_2$* ⋮ *$u_M$* *$v_M$*

1≤N≤1×$10^3$
0≤M≤min(1×$10^3$,$\frac{N(N−1)}{2}$)
1≤$u_i$,$v_i$≤N
给定图无重边和自环。
给定图中每个顶点的度最多为 10 。
输入值均为整数。

输出格式

打印答案。

样例

样例输入 1

样例输出 1

1

3

我们有以下三条路径。（注意，长度为 0 的路径也算在内）。

顶点 1 ；
顶点 1 ，顶点 2 ；
顶点 1 ，顶点 2 ，顶点 3 。

样例输入 2

样例输出 2

1

16

代码长度限制:16 KB

时间限制:1000 ms

内存限制:256 MB

栈限制:8192 KB

answer

这一题由于数据量较小,直接dfs暴力搜索加剪枝即可,但是注意不要用lambda表达式,会出现超时.

 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


#include <bits/stdc++.h>
#define rep(i,a,b) for(ll i=a; i<=b; i++)
#define endl "\n"
//#define MOD 
using namespace std;
using vll = vector<long long>;
using ll = long long;
using ull = unsigned long long;

void dfs(vector<vll> &g,vector<bool> &mp,ll &ans,ll a){
    mp[a]=1;
    ans++;
    if(ans==1e6) return;
    for(auto i:g[a]){
        if(mp[i]) continue;
        dfs(g,mp,ans,i);
        mp[i]=0;
        if(ans==1e6) return;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    ll n,m;
    cin>>n>>m;
    vector<vll> g(n+1);
    vector<bool> mp(n+1,0);
    while(m--){
        ll a,b;
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    ll ans=0;
    dfs(g,mp,ans,1);
    cout<<ans;
    return 0;
}

F.RainbowDash 的数字游戏

题目描述

将 1 到 1018 这些数字按照以下规则依次填充：

从第 1 条斜线开始填充，第 i 条斜线从 (1,i) 到 (i,1)，每个单元格按顺序依次填写一个数字，当第 i 条斜线填充完毕后，填写第 i+1 条斜线，直到 1018 个数字全部填写完毕。规定左上角的位置坐标为 (1,1)，对于接下来的每次询问，请你回答被询问的数字的坐标是多少。

下图展示了左上角 7×7 大小的方格的填写情况。

输入格式:

第一行一个整数 q (1≤q≤$10^5$)，表示询问的次数；

接下来 q 行，每行一个整数 x (1≤x≤$10^18$)，表示询问的数字。

输出格式:

输出共 q 行，每行两个整数 x,y，表示被询问的数字的坐标。

样例

输入样例:

输出样例:

代码长度限制:16 KB

时间限制:1000 ms

内存限制:128 MB

栈限制:8192 KB

answer

这一题当时思考了许久,还是后来将它们前几个数字的坐标列出来之后才发现规律的:

1
2
3
4
5
6


1 (1,1)
2 (1,2)
3 (2,1)
4 (1,3)
5 (2,2)
6 (3,1)

将这些数字按1,2,3,…个分下去可以发现他们的纵坐标递增,横坐标递减.我们只需要找这个数处于那个区间就ok了,这个可以通过开方2n来找(此题要注意用long long否则存不下,还有一点它填充的是一个三角形而不是矩形).

 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


#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        ll m=sqrt(2*n);
        while(!(n>=(m*(m-1)/2)&&n<=(m*(m+1)/2))){
            m--;
        }
        ll x=1,y=m;
        m=m*(m-1)/2;
        x+=n-m-1;
        y-=n-m-1;
        cout<<x<<" "<<y<<endl;
    }
    return 0;
}

G.LilaS 的抛硬币

题目描述

LilaS 最近迷上了抛硬币，闲来没事就想抛两下，有的时候甚至拉着旁边的人一起抛。这天，LilaS 找了 N 个人来抛硬币，每个人抛的次数不一定相同（有的人在偷懒），对于第 i 个人来说，他抛硬币得到的结果是 $A_i$次正面和$B_i$次反面。 LilaS 想计算一下谁的运气比较好，谁的运气比较差。他对运气做了定量化的计算：第 i 个人掷硬币的运气定义为 $\frac{A_i}{A_i+B_i}$ 。现在 LilaS 想让你给这 N 个人的运气排个序，计算量太大了，所以 LilaS 只能求助于你。你能帮帮 LilaS 吗？

输入格式

输入格式如下，其中同一行的每个符号间用空格隔开

N $A_1$ $B_1$ ⋮ $A_N$ *$B_N$*

2≤N≤1000
0≤$A_i$,$B_i$≤$10^9$
$A_i$+$B_i$≥1
所有输入值均为整数。

输出格式

按运气降序输出编号，运气相同的按编号升序输出。

样例

样例输入 1

样例输出 1

1

2 3 1

第 1 个人的运气是 0.25 ，第 2 个人的运气是 0.75 ，第 3 个人的运气是 0.5 。按运气从高到低排序即可得到答案。

样例输入 2

样例输出 2

1

1 2

请注意， 1 和 2 应按编号升序打印，因为它们的运气相同。

样例输入 3

1
2
3
4
5


4
999999999 1000000000
333333333 999999999
1000000000 999999997
999999998 1000000000

样例输出 3

1

3 1 4 2

代码长度限制:16 KB

时间限制:1000 ms

内存限制:512 MB

栈限制:8192 KB

answer

这一题不难,直接计算他们的运气来排序就行.

 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>
#define rep(i,a,b) for(ll i=a; i<=b; i++)
#define endl "\n"
//#define MOD 
using namespace std;
using vll = vector<long long>;
using ll = long long;
using ull = unsigned long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    ll n;
    cin>>n;
    vector<pair<pair<ll,ll>,ll>> num(n);
    rep(i,0,n-1){
        cin>>num[i].first.first>>num[i].first.second;
        num[i].second=i+1;
    }
    sort(num.begin(),num.end(),[](auto a,auto b)-> bool {
        ll a1=a.first.first,a2=a.first.second;
        ll b1=b.first.first,b2=b.first.second;
        ll sa=a1+a2,sb=b1+b2;
        if(a1*1.0/sa==b1*1.0/sb){
            return a.second<b.second;
        }
        return a1*1.0/sa>b1*1.0/sb;
    });
    rep(i,0,n-1){
        cout<<num[i].second<<" ";
    }
    return 0;
}

H.RainbowDash 的 Robot(未完成)

题目描述

对于一个 n×m 大小的二维网格，行的编号从上往下依次为 1 至 n，列的编号从左到右依次为 1 至 m。在第 i 列中，前 $a_i$ 个单元格被阻断，无法通行，其余 n−$a_i$ 个单元格可以通行。换句话说，第 i 列不可以通行的单元格的行的编号的范围是 [1,$a_i$]。

一个机器人正在这个网格内移动，你可以向它发送指令，使得其向上、向右、向下或向左移动。如果机器人试图移动到受阻的单元格或网格外，它就会爆炸。

然而，机器人是有缺陷的，它接收到的每条指令都要执行 k 次。因此，如果你让它向上移动，它会向上移动 k 个单元格，其他方向同理。在机器人执行当前指令时，您不能向它发送新的指令，即机器人需要将当前指令处理完毕，才可以处理下一条指令。

有 q 次询问，每次询问都有一个起始单元、一个终点单元和一个值 k。如果机器人执行每条命令 k 次，能否向它发送任意数量的命令(可能是零)，使它从起点单元到达终点单元？

需要注意的是，机器人在执行完若干条指令后，必须停在终点区。如果机器人仍在执行命令时到达终点区域，则不算数。

输入格式:

第一行输入两个整数 n 和 m (1≤n≤$10^9$，1≤m≤2×$10^5$)，表示网格的行数和列数；

第二行输入 m 个整数 $a_1$,$a_2$,…,$a_m$ (0≤$a_i$≤n)，表示第 i 列阻塞单元格的数量；

第三行输入一个整数 q (1≤q≤2⋅$10^5$)，表示查询次数；

接下来 q 行，每行五个整数 $x_s$,$y_s$,$x_f$,$y_f$,k (a[$y_s$]<$x_s$≤n，1≤$y_s$≤m，a[$y_f$]<$x_f$≤n，1≤$y_f$≤m，1≤k≤$10^9$)，分别表示起点单元格的行和列、终点单元格的行和列，每条命令的执行次数。

题目保证每次查询的起点单元格和终点单元格都是可以通行的。

输出格式:

输出共 q 行。

对于每次查询，如果您能向机器人发送任意数量的命令(可能为零)，使其从起点单元到达终点单元，且每条命令都执行 k 次，输出Yes；否则，输出No。

样例

输入样例:

1
2
3
4
5
6
7
8
9


11 10
9 0 0 10 3 4 8 11 10 8
6
1 2 1 3 1
1 2 1 3 2
4 3 4 5 2
5 3 11 5 3
5 3 11 5 2
11 9 9 10 1

输出样例:

1
2
3
4
5
6


Yes
No
No
No
Yes
Yes

代码长度限制:16 KB

Python (python3)

时间限制:4000 ms

内存限制:512 MB

其他编译器

时间限制:2000 ms

内存限制:256 MB

栈限制:8192 KB

answer

I.LilaS 的逻辑表达式

题目描述

请注意本题不寻常的时间与空间限制！

给出 N 个字符串 $S_1$,…,$S_N$ ，每个字符串都是 AND 或 OR。

求由 N+1 个变量 ($x_0$,…,$x_N$) 构成的序列的个数（其中每个元素都是 True 或 False ）使得经过该序列计算后得到的 $y_N$ 为 True ，计算规则如下：

$y_0$=$x_0$ ;
为 i≥1 ，如果 $S_i$为 AND，则为 $y_i$=$y_{i−1}$∧$x_i$，如果 $S_i$为 OR，则为 $y_i$=$y_{i−1}$∨$x_i$ 。

这里， a∧b 和 a∨b 是逻辑运算符。

输入格式

输入格式如下所示：

N *$S_1$* ⋮ *$S_N$*

1≤N≤60
$S_i$ 是 AND 或 OR。

输出格式

输出满足题目条件序列的个数。

样例

样例输入 1

1
2
3


2
AND
OR

样例输出 1

1

5

如果是 ($x_0$,$x_1$,$x_2$)=(True,False,True) ，则有 $y_2$=True ，如下所示：

$y_0$=$x_0$=True
$y_1$=$y_0$∧$x_1$=True∧False=False
$y_1$=$y_1$∨$x_2$=False∨True=True

所有满足条件的序列 ($x_0$,$x_1$,$x_2$) 如下所示：

(True,True,True)
(True,True,False)
(True,False,True)
(False,True,True)
(False,False,True)

样例输入 2

1
2
3
4
5
6


5
OR
OR
OR
OR
OR

样例输出 2

1

63

代码长度限制:16 KB

时间限制:200 ms

内存限制:32 MB

栈限制:8192 KB

answer

这一题是动态规划,也可以通过递归来写,但是有内存限制只有动态规划可以过.

动态规划思路:记前面所有之和为a,后面填的数字为b,动态规划从后往前推

开始时如果是OR当b=1是a可以为任意值,前面的可以随便组合,所以结果加上$2^i$,当b=0时要a=1,状态转移到前面即可;

开始如果时AND的话只有a=b=1时才满足,向前转移即可.

所以再后面的过程中所转移到的无论是AND还是OR所需求得值均为1,同上即可.

所以从后向前遍历当遇到OR时ans加$2^i$即可.

(发现此题建议自己写一个mypow,我用自带的好像无法过全部测试)

 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


#include <bits/stdc++.h>
#define rep(i,a,b) for(ll i=a; i<=b; i++)
#define endl "\n"
//#define MOD 
using namespace std;
using vll = vector<long long>;
using ll = long long;
using ull = unsigned long long;

ll mypow(ll a,ll b){
    ll ans=1;
    while(b--){
        ans*=a;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    ll n;
    cin>>n;
    vector<string> in(n);
    rep(i,0,n-1){
        cin>>in[i];
    }
    ll ans=1;
    for(ll i=n-1;i>=0;i--){
        if(in[i]=="AND") continue;
        ans+=mypow(2,i+1);
    }
    cout<<ans;
    return 0;
}

J.数字转换大师

题目描述

LilaS 是数字转换大师，他尤其擅长解决下面这类问题：给你一个正整数 N 。

按照下面的规则将正整数 N 转换为长度为 N+1 的字符串 $s_0$ $s_1$…$s_N$ ：

对于每一个整数 i=0,1,2,…,N，在 1 至 9 之间选择一个整数 j，若 N 是 j 的倍数，同时 i 是 N/j 的倍数，则 $s_i$ 是符合条件的最小的 j；如果不存在这样的 j，那么 $s_i$ 为 -。

输入格式

输入格式如下：

N

1≤N≤1000
所有输入值均为整数。

输出格式

输出转换得到的字符串 $s_0$ $s_1$…$s_N$ 。

样例

样例输入 1

1

12

样例输出 1

1

1-643-2-346-1

样例解释

我们将解释如何确定某些 i 的 $s_i$ 。

对于 i=0 来说，所有符合条件介于 1 与 9 之间的整数 j 有 1,2,3,4,6， N/j 对应的值是 12,6,4,3,2。其中 0 是任意数字的倍数(×0)，因此取最小的 j=1 。
对于 i=4 ，所有符合条件介于 1 与 9 之间的整数 j 有 3,6， N/j 对应的值是 4,2。其中对应最小的 j 是 3 ，所以是 $s_4$= 3。
对于 i=6 ，所有符合条件介于 1 与 9 之间的整数 j 有 2,4,6， N/j 对应的值是 6,3,2。其中对应最小的 j 是 2 ，所以是 $s_6$= 2。
对于 i=11 ，不存在 i（11）是 N/j（12,6,4,3,2）的倍数，所以是 $s_11$= -。

样例输入 2

1

7

样例输出 2

1

17777771

样例输入 3

1

1

样例输出 3

1

11

代码长度限制:16 KB

时间限制:1000 ms

内存限制:128 MB

栈限制:8192 KB

answer

这一题直接按照题意将$s_0$到$s_N$求出来即可.

 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


#include <bits/stdc++.h>
#define rep(i,a,b) for(ll i=a; i<=b; i++)
#define endl "\n"
//#define MOD 
using namespace std;
using vll = vector<long long>;
using ll = long long;
using ull = unsigned long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int n;
    cin>>n;
    rep(i,0,n){
        bool ok=1;
        rep(j,1,9){
            if(n%j==0&&i%(n/j)==0){
                cout<<j;
                ok=0;
                break;
            }
        }
        if(ok) cout<<"-";
    }
    return 0;
}

K.LilaS的特殊图判断

题目描述

LilaS 在课堂上刚学了图的定义，于是想要试着写一些图论相关的问题。

现在，LilaS手中有一个无向图，图中有 N 个顶点，编号为 1 ~ N ， M 条边，编号为 1 ~ M 。第 i 条边连接顶点 $u_i$ 和顶点 $v_i$ 。

LilaS 在想有没有一种算法能快速判断该无向图中的每个连通部分是否满足以下条件：

连通部分的顶点和边的数量相同。

注

无向图是指图中的边没有方向。一个图的子图是由该图的顶点和边的子集组成的图。

输入格式

输入格式如下，其中同一行的每个符号间用空格隔开：

N M *$u_1$* *$v_1$* ⋮ *$u_M$* *$v_M$*

1≤N≤$2×10^5$
0≤M≤2×$10^5$
1≤$u_i$≤$v_i$≤N
输入值均为整数。

输出格式

如果该图中每个连通部分都满足条件，则输出 Yes；否则，输出 No。

样例

样例输入 1

样例输出 1

1

Yes

该图有一个由顶点 1 形成的连通部分，以及另一个由顶点 2 和 3 形成的连通部分。
前者有一条边（边 2 ），后者有两条边（边 1 和 3 ），满足条件。

样例输入 2

样例输出 2

1

Yes

样例输入 3

样例输出 3

1

No

代码长度限制:16 KB

时间限制:1000 ms

内存限制:1024 MB

栈限制:8192 KB

answer

这一题我的思路是直接bfs去找联通区块,来记录每个区块联通的点的数量以及边的数量,再进行判断.(当时时间不多了在弄这道题时虽然有思路但根本没写出来,这是下来的时候写的,同时也要注意尽量不要邻接矩阵—-会爆内存)

 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


#include <bits/stdc++.h>
#define rep(i,a,b) for(ll i=a; i<=b; i++)
#define endl "\n"
//#define MOD 
using namespace std;
using vll = vector<long long>;
using ll = long long;
using ull = unsigned long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    ll n,m;
    cin>>n>>m;
    vector<vll> lt(n+1);
    while(m--){
        ll a,b;
        cin>>a>>b;
        lt[a].push_back(b);
        lt[b].push_back(a);
    }
    vector<bool> mp(n+1,0);
    bool ok=1;
    rep(i,1,n){
        if(mp[i]) continue;
        ll a=0,b=0;
        queue<ll> qu;
        qu.push(i);
        mp[i]=1;
        while(!qu.empty()){
            ll num=qu.front();
            qu.pop();
            a++;
            for(auto j:lt[num]){
                b++;
                if(!mp[j]){
                    mp[j]=1;
                    qu.push(j);
                }
            }
        }
        if(a!=b/2){
            ok=0;
            break;
        }
    }
    if(ok) cout<<"Yes";
    else cout<<"No";
    return 0;
}

L.LilaS 与数字交换(未完成)

题目描述

LilaS 上课不认真听讲，被老师逮个正着，为了惩罚他，老师为 LilaS 出了一道题: 给你两个由 N 个数字组成的序列： A=($A_1$,$A_2$,…,*$A_N$) 和 B=(B_1$,$B_2$,…,$B_N$*) 。 LilaS 可以重复下面的操作任意多次（可能为零次）。

在 1 ~ N 之间选择三个不同整数 i ， j 和 k 。
交换 *$A_i$* 和 *$A_j$* ，交换 *$B_i$* 和 *$B_k$*。

现在老师给了 LilaS 依托又臭又长的数组，想让 LilaS 判断是否有办法重复执行上述操作使 A 和 B 相等。

这里，对于每一个 1≤i≤N ，均有 $A_i$=$B_i$ ，则序列 A 和 B 相等。

LilaS 显然不知道这题该怎么写，但是老师要明天检查，所以 LilaS 只能想你求助。你能帮帮 LilaS 吗？

输入格式

输入格式如下，其中同一行的每个符号间用空格隔开

N *$A_1$* *$A_2$* … *$A_N$* *$B_1$* *$B_2$* … *$B_N$*

3≤N≤2×$10^5$
1≤$A_i$,$B_i$≤2×$10^5$
所有输入值均为整数。

输出格式

如果 LilaS 有办法重复执行操作使 A 和 B 相等，则输出Yes；否则，输出 No。

样例

样例输入 1

样例输出 1

1

Yes

用 (i,j,k)=(1,2,3) 执行一次操作，交换 A1 和 A2 ，并交换 B1 和 B3 、使 A 和 B 都等于 (2,1,3) 。因此，您应该输出 Yes。

样例输入 2

样例输出 2

1

Yes

样例输入 3

1
2
3


8
1 2 3 4 5 6 7 8
7 8 5 6 4 3 1 2

样例输出 3

1

No

无法执行使 A 和 B 相等的操作，因此应该输出 No。

样例输入 4

样例输出 4

1

Yes

样例输入 5

样例输出 5

1

No

代码长度限制:16 KB

时间限制:1000 ms

内存限制:1024 MB

栈限制:8192 KB

answer

M.RainbowDash 的整除问题

题目描述

给定两个整数 a,b，每次修改可以使得 a 增加 1，即用 a+1 替换 a，你的目标是让 a 变成 b 的倍数，请问最小修改次数是多少。

输入格式:

第一行输入一个整数 T (1≤T≤$10_4$)，表示测试用例组数。

接下来 T 行，每行两个整数 a,b (1≤a,b≤$10_6$)。

输出格式:

输出共 T 行，每行一个整数，表示每组测试用例的最小修改次数。

样例

输入样例:

输出样例:

代码长度限制:16 KB

时间限制:1000 ms

内存限制:128 MB

栈限制:8192 KB

answer

这一题可以通过找出大于a的b的最小倍数,再相减即可计算出结果.

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


#include <bits/stdc++.h>
#define rep(i,a,b) for(ll i=a; i<=b; i++)
#define endl "\n"
//#define MOD 
using namespace std;
using vll = vector<long long>;
using ll = long long;
using ull = unsigned long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    ll t;
    cin>>t;
    while(t--){
        ll a,b;
        cin>>a>>b;
        ll n=b;
        while(n<a) n+=b;
        cout<<n-a<<endl;
    }
    return 0;
}