2021年度训练联盟热身训练赛第四场，签到题CDF
概述
题号 标题 已通过代码 通过率 团队的状态
A Broadcast Stations 点击查看 17/55 未通过
B Connect3 点击查看 167/234 未通过
C Game Map 点击查看 645/2356 通过（图论爆搜）
D Happy Number 点击查看 1177/1908 通过（数字枚举）
E How Many to Be Happy? 点击查看 19/103 未通过
F Philosopher‘s Walk 点击查看 433/1283 通过（分形图或模拟）
G Rectilinear Regions 点击查看 5/26 未通过
H Rock Paper Scissors 点击查看 58/410 未通过
I Slot Machines 点击查看 354/1866 通过（KMP，队友开的）
J Strongly Matchable 点击查看 4/57 未通过
K Untangling Chain 点击查看 159/353 未通过
L Vacation Plans 点击查看 8/83 未通过
C Game Map
链接：https://ac.nowcoder.com/acm/contest/13506/C
来源：牛客网
题目描述
输入描述:
输出描述:
示例1
输入
复制
6 9
0 1
0 4
1 2
1 3
1 4
1 5
2 5
3 4
4 5
输出
复制
4
示例2
输入
复制
12 11
1 2
2 3
3 4
4 5
5 0
6 3
7 4
8 5
9 4
10 5
11 5
输出
复制
5
//题意：给出n个点m条边的无向图，每次只能从度数小的点向度数大的点走，求图中的最长路
//思路：新建一个有向图，从度数小的往大的连有向边，从每个入度为0的节点开始dfs，搜最长链并统计
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+10;
vector<int>G[maxn],G2[maxn];
int vis[maxn],in[maxn], tmp = 0;
void dfs(int u,int h){
tmp = max(tmp,h);
for(int v:G2[u]){
if(vis[v])continue;
vis[v] = 1;
dfs(v,h+1);
vis[v] = 0;
}
}
int main(){
ios::sync_with_stdio(false);
int n, m;
cin>>n>>m;
for(int i = 0; i < m; i++){
int x, y; cin>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
queue<int>q;
for(int i = 0; i < n; i++){
for(int u : G[i]){
if(G[u].size()<G[i].size()){
in[i]++;
G2[u].push_back(i);
}
}
if(in[i]==0)q.push(i);
}
int ans = 0;
while(q.size()){
int u = q.front(); q.pop();
dfs(u,1);
ans = max(ans,tmp);
}
cout<<ans<<"\n";
return 0;
}
- 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
D. Happy Number
Happy Number
比赛主页
团队提交
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld
题目描述
输入描述:
输出描述:
示例1
输入
复制
19
输出
复制
HAPPY
示例2
输入
复制
5
输出
复制
UNHAPPY
//题意：给出一个数n，每次令n=n的位数平方和，若最后能变成1那就是快乐数，不能就是不快乐。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main(){
LL x; cin>>x;
set<LL>se;
int ok = 1;
while(1){
LL sum = 0;
while(x>0){ LL k=x%10; sum+=k*k; x/=10;}
if(se.count(sum)){
ok = 0; break;
}
LL tmp = sum;
while(tmp%10==0){tmp/=10;}
if(tmp==1){
ok = 1; break;
}
se.insert(sum);
x = sum;
}
if(ok==1)cout<<"HAPPY\n";
else cout<<"UNHAPPY\n";
return 0;
}
- 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
F. Philosopher‘s Walk
链接：https://ac.nowcoder.com/acm/contest/13506/F
来源：牛客网
题目描述
输入描述:
输出描述:
示例1
输入
复制
4 10
输出
复制
3 4
示例2
输入
复制
8 19
输出
复制
2 6
//题意：模拟画图
//思路：分形图或者直接模拟，没开longlong改了一个多小时
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000010;
typedef long long LL;
LL x=1, y=1, dir=0;
//当前在边长为n的正方形，第k个子正方形中的第res个，子正方形的方向是dir，1表示顺时针，-1表示逆时针，0表示不动，2表示反转
void dfs(LL n, LL k, LL res){
//cout<<n<<" "<<dir<<" "<<k<<" "<<res<<":"<<x<<" "<<y<<"\n";
if(n==2){
//return ;
//cout<<n<<" "<<dir<<" "<<k<<" "<<res<<":"<<x<<" "<<y<<"\n";
return ;
}
//cout<<n<<" "<<dir<<" "<<k<<" "<<res<<":"<<x<<" "<<y<<"\n";
LL n4 = n*n/4/4;//子正方形的点数
if(dir==0){
if(res>n4*3){
dir=-1;//dir--;
x += n/4;
dfs(n/2,4,res-n4*3);
}else if(res>n4*2){
dir = 0;
x += n/4; y+=n/4;
dfs(n/2,3,res-n4*2);
}else if(res>n4){
dir = 0;
y+=n/4;
dfs(n/2,2,res-n4);
}else{
dir=1;//dir++;
dfs(n/2,1,res);
}
}else if(dir==1){
if(res>n4*3){
dir=2;//dir++;//
y += n/4;//y += n/4;
dfs(n/2,4,res-n4*3);
}else if(res>n4*2){
dir=1;//dir++;//dir = 0;
x += n/4; y+=n/4;
dfs(n/2,3,res-n4*2);
}else if(res>n4){
dir=1;//dir++; //dir = 0;
x+=n/4;
dfs(n/2,2,res-n4);
}else{
dir = 0;//dir--;
dfs(n/2,1,res);
}
}else if(dir==-1){
if(res>n4*3){
dir = 0;//dir=1;//dir--;
x += n/4; //y+=n/4;
dfs(n/2,4,res-n4*3);
}else if(res>n4*2){
dir=-1;//dir = 0;
//y+=n/4;
dfs(n/2,3,res-n4*2);
}else if(res>n4){
dir=-1;//dir = 0;
y+=n/4;//x+=n/4;
dfs(n/2,2,res-n4);
}else{
x+=n/4;y+=n/4;
dir = 2;//dir++;
dfs(n/2,1,res);
}
}else if(dir==2){
if(res>n4*3){
dir = 1;
y += n/4;
dfs(n/2,4,res-n4*3);
}else if(res>n4*2){
dir=2;
dfs(n/2,3,res-n4*2);
}else if(res>n4){
dir=2;
x+=n/4;
dfs(n/2,2,res-n4);
}else{
dir = -1;
x += n/4; y+=n/4;
dfs(n/2,1,res);
}
}
}
int main(){
ios::sync_with_stdio(false);
LL n, m; cin>>n>>m;
dfs(n*2,1, m);
cout<<x<<" "<<y<<"\n";
//cout<<y<<" "<<x<<"\n";
return 0;
}
- 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
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
本题数据
4 10
3 4
8 19
2 6
4 13
4 2
8 15
1 3
8 49
8 4
8 52
7 4
8 56
6 3
8 64
8 1
16 256
16 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
文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。
原文链接：gwj1314.blog.csdn.net/article/details/115285351
- 点赞
- 收藏
- 关注作者
评论（0）