博罗东莞网站建设,定制网站建设费用预算,传奇免费网站建设,网站被k的迹象蒟蒻来讲题#xff0c;还望大家喜。若哪有问题#xff0c;大家尽可提#xff01;
Hello, 大家好哇#xff01;本初中生蒟蒻讲解一下AtCoder Beginner Contest 292这场比赛的A-E题#xff01; A题
原题
Problem Statement
You are given a string SSS consisting of lo…蒟蒻来讲题还望大家喜。若哪有问题大家尽可提
Hello, 大家好哇本初中生蒟蒻讲解一下AtCoder Beginner Contest 292这场比赛的A-E题 A题
原题
Problem Statement
You are given a string SSS consisting of lowercase English letters. Uppercase each character of SSS and print the resulting string TTT.
Constraints
SSS is a string consisting of lowercase English letters whose length is between 111 and 100100100, inclusive.
Input
The input is given from Standard Input in the following format: SSS
Output
Print TTT.
Sample Input 1
abc
Sample Output 1
ABC Uppercase each character of abc, and you have ABC.
Sample Input 2
a
Sample Output 2
A
Sample Input 3
abcdefghjiklnmoqprstvuwxyz
Sample Output 3
ABCDEFGHJIKLNMOQPRSTVUWXYZ
思路
水题一道不多写啦
代码
/*
------------------Welcome to Your Code--------------
Name:
Contest:AtCoder Beginner Contest 292
Wishes:AK!
------------------Start Writing!!!------------------
*/
#include iostream
#define endl \n
#define pb(i) push_back(i)using namespace std;inline int read()
{int w 1, s 0;char c getchar();while (c 0 || c 9){if (c -) w -1;c getchar();}while (c 0 c 9) s s * 10 c - 0, c getchar();return w * s;
}int main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);string s;cin s;for (auto c : s)cout char(c - a A);return 0;
}B题
原题
Problem Statement
NNN players numbered 111 to NNN will play a soccer game. When a player commits an offense, that player will receive a yellow card or a red card. A player who satisfies one of the following conditions will be removed from the game. Accumulates two yellow cards. Receives a red card. Once a player is removed, that player will no longer receive any cards. You will watch this game. Initially, the players have not received any cards. There will be QQQ events. Correctly answer the questions asked in the events. There are three kinds of events, which are given in the format c x from the input, where ccc is 111, 222, or 333. The events are as follows. 1 x: Player xxx receives a yellow card. 2 x: Player xxx receives a red card. 3 x: You are asked whether player xxx has been removed from the game. Answer Yes or No.
Constraints
1≤N≤1001 \leq N \leq 1001≤N≤100 1≤Q≤1001 \leq Q \leq 1001≤Q≤100 1≤x≤N1 \leq x \leq N1≤x≤N in all events. There is at least one event of the third kind. A player who has been removed will no longer receive any cards. All values in the input are integers.
Input
The input is given from Standard Input in the following format, where eventi\text{event}_ieventi denotes the iii-th event. NNN QQQ event1\text{event}_1event1 event2\text{event}_2event2 ⋮\vdots⋮ eventQ\text{event}_QeventQ Each event is in one of the following formats: 1 xxx 2 xxx 3 xxx
Output
Print XXX lines, where XXX is the number of events of the third kind in the input. The iii-th line should contain Yes if, for the iii-th event of the third kind, player xxx has been removed from the game, and No otherwise.
Sample Input 1
3 9 3 1 3 2 1 2 2 1 3 1 3 2 1 2 3 2 3 3
Sample Output 1
No No Yes No Yes No Here are all the events in chronological order. In the 111-st event, you are asked whether player 111 has been removed from the game. Player 111 has not been removed, so you should print No. In the 222-nd event, you are asked whether player 222 has been removed from the game. Player 222 has not been removed, so you should print No. In the 333-rd event, player 222 receives a yellow card. In the 444-th event, player 111 receives a red card and is removed from the game. In the 555-th event, you are asked whether player 111 has been removed from the game. Player 111 has been removed, so you should print Yes. In the 666-th event, you are asked whether player 222 has been removed from the game. Player 222 has not been removed, so you should print No. In the 777-th event, player 222 receives a yellow card and is removed from the game. In the 888-th event, you are asked whether player 222 has been removed from the game. Player 222 has been removed, so you should print Yes. In the 999-th event, you are asked whether player 333 has been removed from the game. Player 333 has not been removed, so you should print No.
思路
也比较水不讲啦直接看代码吧
代码
/*
------------------Welcome to Your Code--------------
Name:
Contest:AtCoder Beginner Contest 292
Wishes:AK!
------------------Start Writing!!!------------------
*/
#include iostream
#define endl \n
#define pb(i) push_back(i)using namespace std;const int N 1e2 10;double st[N];inline int read()
{int w 1, s 0;char c getchar();while (c 0 || c 9){if (c -) w -1;c getchar();}while (c 0 c 9) s s * 10 c - 0, c getchar();return w * s;
}int main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int n, q;cin n q;while (q --){int op, x;cin op x;if (op 1) st[x] 0.5;else if (op 2) st[x] ;else{cout (st[x] 1 ? Yes : No) endl;}}return 0;
}C题
原题
Problem Statement
You are given a positive integer NNN. Find the number of quadruples of positive integers (A,B,C,D)(A,B,C,D)(A,B,C,D) such that ABCDNAB CD NABCDN. Under the constraints of this problem, it can be proved that the answer is at most 9×10189 \times 10^{18}9×1018.
Constraints
2≤N≤2×1052 \leq N \leq 2 \times 10^52≤N≤2×105 NNN is an integer.
Input
The input is given from Standard Input in the following format: NNN
Output
Print the answer.
Sample Input 1
4
Sample Output 1
8 Here are the eight desired quadruples. (A,B,C,D)(1,1,1,3)(A,B,C,D)(1,1,1,3)(A,B,C,D)(1,1,1,3) (A,B,C,D)(1,1,3,1)(A,B,C,D)(1,1,3,1)(A,B,C,D)(1,1,3,1) (A,B,C,D)(1,2,1,2)(A,B,C,D)(1,2,1,2)(A,B,C,D)(1,2,1,2) (A,B,C,D)(1,2,2,1)(A,B,C,D)(1,2,2,1)(A,B,C,D)(1,2,2,1) (A,B,C,D)(1,3,1,1)(A,B,C,D)(1,3,1,1)(A,B,C,D)(1,3,1,1) (A,B,C,D)(2,1,1,2)(A,B,C,D)(2,1,1,2)(A,B,C,D)(2,1,1,2) (A,B,C,D)(2,1,2,1)(A,B,C,D)(2,1,2,1)(A,B,C,D)(2,1,2,1) (A,B,C,D)(3,1,1,1)(A,B,C,D)(3,1,1,1)(A,B,C,D)(3,1,1,1)
Sample Input 2
292
Sample Output 2
10886
Sample Input 3
19876
Sample Output 3
2219958 思路
这道题我们可以枚举ABABAB假设为iii那么CDCDCD就是n−in - in−i之后先计算约数的个数如果是个奇数那么就说明中间有个数是相同的所以要特判。最后答案就把各种情况列出来相加令nab为AB的约数的个数ncd为CD的约数的个数
若nabncd都为偶数则此时的方案数nab×ncdnab\times ncdnab×ncd若nabncd都为奇数则此时的方案数(nab−1)(ncd−1)nanc1(nab-1)(ncd-1)nanc1(nab−1)(ncd−1)nanc1可能有点难理解自己推一下就可以啦若还是不懂联系我即可若nab为偶数ncd为奇数则此时的方案数nab(ncd−1)nc∗2nab(ncd-1)nc*2nab(ncd−1)nc∗2
最后把所有的方案数相加就是最终的答案了 代码时间复杂度O(NN)O(N\sqrt{N})O(NN)
/*
------------------Welcome to Your Code--------------
Name:
Contest:AtCoder Beginner Contest 292
Wishes:AK!
------------------Start Writing!!!------------------
*/
#include iostream
#include cmath
#define endl \n
#define pb(i) push_back(i)using namespace std;int res;inline int read()
{int w 1, s 0;char c getchar();while (c 0 || c 9){if (c -) w -1;c getchar();}while (c 0 c 9) s s * 10 c - 0, c getchar();return w * s;
}int get_divides(int n) //求约数的个数
{int counts 0;for (int i 1; i * i n; i){if (n % i 0){if (i * i n) counts;elsecounts 2;}}return counts;
}int main()
{int n;cin n;long long ans 0;for (int i 1; i n; i ){int ab i, cd n - i;int na,nab get_divides(ab);bool fab 0;int nc,ncd get_divides(cd);bool fcd 0;if(nab % 2) na nab -1,fab 1;else na nab;if(ncd % 2) nc ncd -1,fcd 1;else nc ncd;if(fab ){if(fcd){ans na * nc na nc 1;}else{ans na * nc nc * 2 ;}}else ans na * nc;}cout ans endl;return 0;
}D题
原题
Problem Statement
You are given an undirected graph with NNN vertices numbered 111 to NNN and MMM edges numbered 111 to MMM. Edge iii connects vertex uiu_iui and vertex viv_ivi. Determine whether every connected component in this graph satisfies the following condition. The connected component has the same number of vertices and edges.
Notes
An undirected graph is a graph with edges without direction. A subgraph of a graph is a graph formed from a subset of vertices and edges of that graph. A graph is connected when one can travel between every pair of vertices in the graph via edges. A connected component is a connected subgraph that is not part of any larger connected subgraph.
Constraints
1≤N≤2×1051 \leq N \leq 2 \times 10^51≤N≤2×105 0≤M≤2×1050 \leq M \leq 2 \times 10^50≤M≤2×105 1≤ui≤vi≤N1 \leq u_i \leq v_i \leq N1≤ui≤vi≤N All values in the input are integers.
Input
The input is given from Standard Input in the following format: NNN MMM u1u_1u1 v1v_1v1 ⋮\vdots⋮ uMu_MuM vMv_MvM
Output
If every connected component satisfies the condition, print Yes; otherwise, print No.
Sample Input 1
3 3 2 3 1 1 2 3
Sample Output 1
Yes The graph has a connected component formed from just vertex 111, and another formed from vertices 222 and 333. The former has one edge (edge 222), and the latter has two edges (edges 111 and 333), satisfying the condition.
Sample Input 2
5 5 1 2 2 3 3 4 3 5 1 5
Sample Output 2
Yes
Sample Input 3
13 16 7 9 7 11 3 8 1 13 11 11 6 11 8 13 2 11 3 3 8 12 9 11 1 11 5 13 3 12 6 9 1 10
Sample Output 3
No 思路
这道题我们就是判断每一个连通块是否点数和边数相等所以我们可以用**洪水填充Flood Fill**算法当然可以用DFS做 代码
/*
------------------Welcome to Your Code--------------
Name:
Contest:AtCoder Beginner Contest 292
Wishes:AK!
------------------Start Writing!!!------------------
*/
#include iostream
#include vectorusing namespace std;const int N 2e5 10;int n, m, edge, vert;
vectorint fg[N];
bool ft[N];inline int read()
{int w 1, s 0;char c getchar();while (c 0 || c 9){if (c -) w -1;c getchar();}while (c 0 c 9) s s * 10 c - 0, c getchar();return w * s;
}void dfs(int u)
{for (auto c : fg[u]){if (!ft[c]){ft[c] 1;edge , vert ;dfs(c);}else edge ;}
}int main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);cin n m;int x, y;for (int i 1; i m; i )cin x y, fg[x].push_back(y), fg[y].push_back(x);for (int i 1; i n; i )if (!ft[i]){vert 1;edge 0;ft[i] 1;dfs(i); //找当前连通块if (edge / 2 ! vert) //因为我是用的无向边所以真正的边数要除以2{cout No endl;return 0;}}cout Yes endl;return 0;
}E题
原题
Problem Statement
You are given a simple directed graph with NNN vertices numbered 111 to NNN and MMM edges numbered 111 to MMM. Edge iii is a directed edge from vertex uiu_iui to vertex viv_ivi. You may perform the following operation zero or more times. Choose distinct vertices xxx and yyy such that there is no directed edge from vertex xxx to vertex yyy, and add a directed edge from vertex xxx to vertex yyy. Find the minimum number of times you need to perform the operation to make the graph satisfy the following condition. For every triple of distinct vertices aaa, bbb, and ccc, if there are directed edges from vertex aaa to vertex bbb and from vertex bbb to vertex ccc, there is also a directed edge from vertex aaa to vertex ccc.
Constraints
3≤N≤20003 \leq N \leq 20003≤N≤2000 0≤M≤20000 \leq M \leq 20000≤M≤2000 1≤ui,vi≤N1 \leq u_i ,v_i \leq N1≤ui,vi≤N ui≠viu_i \neq v_iuivi (ui,vi)≠(uj,vj)(u_i,v_i) \neq (u_j,v_j)(ui,vi)(uj,vj) if i≠ji \neq jij. All values in the input are integers.
Input
The input is given from Standard Input in the following format: NNN MMM u1u_1u1 v1v_1v1 ⋮\vdots⋮ uMu_MuM vMv_MvM
Output
Print the answer.
Sample Input 1
4 3 2 4 3 1 4 3
Sample Output 1
3 Initially, the condition is not satisfied because, for instance, for vertices 222, 444, and 333, there are directed edges from vertex 222 to vertex 444 and from vertex 444 to vertex 333, but not from vertex 222 to vertex 333. You can make the graph satisfy the condition by adding the following three directed edges: one from vertex 222 to vertex 333, one from vertex 222 to vertex 111, and one from vertex 444 to vertex 111. On the other hand, the condition cannot be satisfied by adding two or fewer edges, so the answer is 333.
Sample Input 2
292 0
Sample Output 2
0
Sample Input 3
5 8 1 2 2 1 1 3 3 1 1 4 4 1 1 5 5 1
Sample Output 3
12 思路
这道题我们完全可以把每个点能到的点的个数都加起来在减去原来就有的边数就是我们没有建出来的边数所以求出这个没有建的边数即可 代码
/*
------------------Welcome to Your Code--------------
Name:
Contest:AtCoder Beginner Contest 292
Wishes:AK!
------------------Start Writing!!!------------------
*/
#pragma GCC optimize(2)
#pragma GCC optimize(3,Ofast,inline)
#include iostream
#include vector
#include cstring
#include queue
#define endl \n
#define pb(i) push_back(i)using namespace std;const int N 2e3 10;int n, m;
bool edge[N][N];
vectorint g[N];
int x, y;
int turn[N];
bool st[N];inline int read()
{int w 1, s 0;char c getchar();while (c 0 || c 9){if (c -) w -1;c getchar();}while (c 0 c 9) s s * 10 c - 0, c getchar();return w * s;
}int bfs(int u)
{memset(st, 0, sizeof st);queueint q;q.push(u);st[u] 1;int res 0;while (q.size()){int t q.front();q.pop();for (auto c : g[t])if (!st[c]){q.push(c);res ;st[c] 1;}}return res;
}int main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);cin n m;for (int i 1; i m; i )cin x y, g[x].pb(y), edge[x][y] 1;int ans 0;for (int i 1; i n; i )ans bfs(i);cout ans - m endl;return 0;
}今天就到这里了
大家有什么问题尽管提我都会尽力回答的
吾欲您伸手点的小赞赞。吾欲您喜欢点得小关注
