A. Abiyoyo、
题意
输出n个
Abiyoyo, Abiyoyo.
在输出两个
Abiyoyo, yo yoyo yo yoyo.
代码
#include<iostream>
using namespace std;
int main(){
int T;
scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
while(n--){
puts("Abiyoyo, Abiyoyo.");
}
puts("Abiyoyo, yo yoyo yo yoyo.");
puts("Abiyoyo, yo yoyo yo yoyo.");
}
return 0;
}
E The Champion
题意
给了r，k，p 三个数，表示一用有 2
r
给人，当前这个人在第k个强，如果强的人和弱的人打获胜的概率为p，求这个人获胜的最大可能
思路
如果一个要想获得胜率的可能性最大，那么他应该尽可能先和比他弱的人打（先和获胜概率大的人比赛，否则这个概率会一直在比赛中间接性的减小），争取强的人淘汰更多强的人，按照这个贪心的思路，如果有弱的人，那么就和弱的人打，就只能和强的人打，那么弱的人应该淘汰的尽可能少，所以弱的和弱的打，强的和强的打，对于有一个弱的和一个强的的情况单独处理，就可以使用dfs的思路，统计每次的剩下的强和弱 人的个数，然后继续递归，直到这个人获胜
代码
#include<iostream>
#include<cstring>
#include<map>
using namespace std;
#define x first
#define y second
typedef pair<int ,int > PII;
#define int long long
int r,k;
double p;
map<PII ,double > mp;
double dfs(int higher,int lower){
if(higher == 0&& lower == 0) return 1; // 没人, 必胜
if(mp.count({higher,lower})) return mp[{higher,lower}]; // 记忆化搜索
auto &v = mp[{higher,lower}];
if(lower & 1){ // 弱的人为奇数，那么和一个弱的人比 获胜概率p
return v = p * dfs(higher/2,lower/2);
}
else{
// 如果 弱的人是偶数，还是和弱的人比，但是就会有一个弱的和强的比较，对应不同的概率和剩余人数
if(lower != 0){
return v = p * (p * dfs(higher/2 + 1,lower/2 - 1) + (1 - p) * dfs(higher/2,lower/2));
}
else{ //如果没有 弱的人，那么只会和强的比较
return v = (1 - p) * dfs(higher/2,0);
}
}
}
signed main(){
int T;
cin>>T;
while(T--){
mp.clear();
scanf("%lld%lld%lf",&r,&k,&p);
r = 1ll<<r; // 总人数
int higher = k - 1,lower = r - k; //强的人数和弱的人数
if(p < 0.5) swap(higher,lower), p = 1 - p; // 如果概率小则交换
double res = dfs(higher,lower);
printf("%.6lf\n",res);
}
return 0;
}
F. The Chosen One
题意
有n个人站成一排，每次会淘汰奇数位置的人，然后在剩余人中继续淘汰，只到最后一个人为为止，求最后一个人的编号
思路
我们在每k次淘汰中只会剩下 2
k
的倍数的人，那么最后一次人的编号就是2
k
，且不存在他的倍数，即不存在2
k+1
这个编号
代码
T = int(input(""))
while T:
T -= 1
n = int(input(""))
ans = 1
while ans * 2 <= n: # 存在就一直运算
ans *= 2
print(ans)
H. The Game of Life
题意
给定几个细胞在无限大的平面上扩展，默认其余细胞都是死的，求在0 – 321次中最多的细胞是哪次，个数为多少，321次有多少个细胞
细胞的成活满足
1.如果活细胞的周围小于2个或大于3个那么他就会死
2.活细胞只有周围有2个或三个才能存活到下一次
3.死细胞的周围有精确地3个就活
思路
就是简单的模拟，但是卡常，一直过不去，参考别人的代码写的
代码
#include<iostream>
#include<cstring>
#include<set>
#include<vector>
using namespace std;
#define x first
#define y second
typedef pair<int ,int > PII;
const int N = 1010,M = 350;
bool a[N][N];
set<PII> s;
vector<PII > live,died;
int dx[] = {1,-1,0,0,1,1,-1,-1};
int dy[] = {0,0,1,-1,1,-1,1,-1};
char str[10];
void insert(int x,int y){
for(int i = -1;i<=1;i++)
for(int j = -1;j<=1;j++)
s.insert({x + i,y + j});
}
int get(int x,int y){
int t = 0;
for(int i = 0;i<8;i++){
int p = x + dx[i],q = y + dy[i];
if(a[p][q]) t++;
}
return t;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
memset(a,0,sizeof a);
s.clear();
int n,m;
scanf("%d%d",&n,&m);
int sum = 0;
for(int i = 0;i < n; i++){
scanf("%s",str);
for(int j = 0;j < m; j++)
{
if(str[j] == '#'){
int x = i + M,y = j + M;
insert(x,y);
sum ++;
a[x][y] = true;
}
}
}
int max_id = 0,max_s = sum;
for(int i = 1;i <= 321;i++){
live.clear();
died.clear();
for(auto it:s){
int x = it.x,y = it.y;
if(a[x][y]){
int t = get(x,y);
if(t == 2||t == 3) continue;
died.push_back({x,y});
sum--;
}
else{
int t = get(x,y);
if(t == 3) live.push_back({x,y}),sum++;
}
}
if(sum > max_s) max_id = i,max_s = sum;
for(auto it:live){
insert(it.x,it.y);
a[it.x][it.y] = true;
}
for(auto it:died){
a[it.x][it.y] = false;
}
}
printf("%d %d %d\n",max_id,max_s,sum);
}
return 0;
}
I. Rake It In
题意
给定一个4 * 4的地方，有两个人，他们分别选一块2 * 2的地方，并把上面的分数加到总分且这四个单元格会逆转，每个人分别操作k次第一个人想让总分最大，第二个人想让总分最小，求最后的总分数
思路
因为每次的范围很小很小，而且单元的也很小就可以直接考虑爆搜，如果第一个人就选择地方的分数 + 他和第二个人之后的操作分数 中最大的那个，第二个也是同样，只不过找分数最小的地方
代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 10;
int g[N][N];
int n;
int dfs(int u){ // u为偶数则认为是第一个人 反正第二个人
if(u == 2 * n) return 0;
int res = 0; // 第一人最大化答案
if(u%2) res = 0x3f3f3f3f; // 第二人 最小化答案
for(int i = 0;i<=2;i++)
for(int j = 0;j<=2;j++)
{
// 逆时针旋转
int a = g[i][j],b = g[i][j + 1];
int c = g[i+1][j],d = g[i + 1][j + 1];
g[i][j] = b,g[i][j + 1] = d,g[i + 1][j + 1] = c,g[i+1][j] = a; //
if(u%2) res = min(res,dfs(u + 1) + a + b + c + d);
else res = max(res,dfs(u + 1) + a + b + c + d);
// 恢复现场
g[i][j] = a,g[i][j+1] = b,g[i + 1][j] = c,g[i + 1][j + 1] = d;
}
return res;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i = 0;i<4;i++)
for(int j = 0;j<4;j++)
scanf("%d",&g[i][j]);
cout<<dfs(0)<<endl;
}
return 0;
}
J. Rearrangement
题意
给定一个2 * n的序列，请对它们重新排列，使得相邻的两个数的之和不是三的倍数
思路
我们可以间接的想，只用考虑%3的余数，其中余数为1和为2的不能相邻，但是他们可以和余数为0的相邻，余数为0的只要不和自己相邻即可
首先，考虑余数为0的不能自己相邻，即余数为0的个数只用不大于n即可
其次，考虑余数为1和为2的不能相邻，那么我们可以把余数为1的放在一边，余数为2的放在另一边中间使用两个余数为0的建立分割线，（剩余的余数为0的可以按照余数为1或余数为2分别处理）如果余数为0的小于两个且余数为1和为2的都存在那么他们必然相邻，
特殊情况 只有2个余数为0时，余数为1的个数必须为奇数，因为隔离的两边都能只能有奇数个
| 1 | 1 | 1 | 0 | 2 | 2 |
|---|---|---|---|---|---|
| 1 | 1 | 0 | 2 | 2 | 2 |
或者
| 1 | 1 | 0 | 2 | 2 | 2 |
|---|---|---|---|---|---|
| 1 | 1 | 1 | 0 | 2 | 2 |
都是奇数个，余数为0大于三可以给余数为1或2自由分配这不需要考虑这种情况
代码
#include<iostream>
#include<cstring>
using namespace std;
int cnt[3];
int main(){
int T;
scanf("%d",&T);
while(T--){
int n;
memset(cnt,0,sizeof cnt);
scanf("%d",&n);
for(int i = 1;i<=2 * n;i++){
int x;
scanf("%d",&x);
int v = x%3;
cnt[v]++; // 统计各自的个数
}
bool flag = true;
if(cnt[0] > n){ // 余数为0大于n
flag = false;
}
if(cnt[0] <= 2 &&(cnt[1]&&cnt[2])){
if(cnt[0] < 2) //小于2且余数为1,2都存在
flag = false;
if(cnt[0] == 2 &&(cnt[1]%2 == 0&&cnt[2]%2==0)){ //等于2 他们都为偶数
flag = false;
}
}
if(flag) puts("YES");
else puts("NO");
}
return 0;
}
L. Twice Equation
题意
给出L，求不小于L的满足 2m(m + 1) = n(n + 1)的最小m
思路
不会推公式，打表加在
推公式网站
上搜
公式 a
0
= 0,a
1
= 3, a
n
= 6 * a
n-1
– a
n-2
+ 2
代码
T = int(input(""))
while T:
T -= 1
n = int(input(""))
a = 0
b = 3
while a < n:
t = 6 * b - a + 2
a = b
b = t
print(a)
M. The Maximum Unreachable Node Set
题意
给定一个DAG（有向图），求有向图的最大独立集，即最大的不可达点集
思路
总个数 – 最小覆盖数，最小覆盖数就是二分图的最大匹配数
可以先用Floyd算法求出所有点的可达点
代码
/*
最小点覆盖 == 最大匹配
*/
#include<iostream>
#include<cstring>
using namespace std;
const int N = 110;
int match[N];
bool st[N];
bool g[N][N];
int n,m;
bool find(int u){
for(int i =1;i<=n;i++){
if(!g[u][i]||st[i]) continue;
int t = match[i];
st[i] = true;
if(t == 0||find(t)){
match[i] = u;
return true;
}
}
return false;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
memset(match,0,sizeof match);
memset(g,0,sizeof g);
scanf("%d%d",&n,&m);
while(m--){
int a,b;
scanf("%d%d",&a,&b);
g[a][b] = true;
}
for(int k = 1;k<=n;k++)
for(int i = 1;i<=n;i++)
for(int j = 1;j<=n;j++)
g[i][j]|=g[i][k]&g[k][j];
int res = 0;
for(int i = 1;i<=n;i++){
memset(st,0,sizeof st);
if(find(i)) res++;
}
printf("%d\n",n - res);
}
return 0;
}