我从这里抄的
题目网址
B - Trick Taking
题目大意
N 位玩家编号为 1,2,…,N。正在玩卡牌游戏，每个人都出了一张牌。 第 i 个人出的牌颜色是 C~i~，等级是 R~i~ 。保证 R~1~,R~2~,…,R~N~各不相等。请判断谁赢了。 赢牌规则如下：
- 如果有至少一张卡牌颜色为 T（给定的目标颜色），那么谁的牌等级高谁就赢。
- 如果没人出颜色 T 的牌，那么==目标颜色为 C~1~== 和 C~1~颜色相同的牌中，等级最高的获胜。
数据范围：
- 2≤N≤2×10^5^
- 1≤T≤10^9^
- 1≤C~i~≤10^9^
- 1≤R~i~≤10^9^
解题思路
在输入颜色的时候，==看看有没有给定的颜色T，有的话就将目标颜色定为T，否则定为C~1~==。 然后在输入等级时记录下目标颜色中最大的。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int ans;
void zzxc(int a,int b){
if(a == b) return ;
if(a % b != 0){
ans += a / b;
zzxc(b, a%b);
}
else {
ans += a / b - 1;
}
}
signed main() {
int a, b;
cin >> a >> b;
zzxc(a,b);
cout << ans;
return 0;
}
C - Dango
题目大意
一个 L 级别的团子为满足下面要求的字符串：
- 长度为 L+1，且只包含
o与-。 - 只有一个
-，其他字符都是o。且 - 是第一个字符或者最后一个字符。
给定一个只包含 o 和 - 的，长度为 N 的字符串 S，如果存在某个子串是团子，就输出最高级别的团子值，否则输出 -1。
数据范围：
- 1≤N≤2×10^5^
解题思路
记录下o和-的数量的同时，记录一下连续的o最长的长度。==最后一个了可能没有记录过，退出循环后还要再判断一次==。最后分情况输出。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
string s;
int sum1, sum2, sum, maxx = -1;
signed main() {
cin >> n;
cin >> s;
for(int i = 0; i <= n - 1; i++){
if(s[i] == 'o') {//记录o的总数和o连续的数量
sum1++;
sum ++;
}
if(s[i] == '-') {//记录-的总数，切断连续并记录下最大的
sum2++;
maxx = max(maxx, sum);
sum = 0;
}
}
maxx = max(maxx, sum);//最后一个可能没有记录过
if(sum1 == 0||sum2 == 0) {//没有o或-，输出-1
cout << -1;
return 0;
}
else {
cout << maxx;
}
return 0;
}
D - Find by Query
题目大意
交互题。 首先输入一个交互器给出的 N。交互器想好了一个确定的字符串 S，保证 S 只包含 0 和 1，且第一个字符是 0，最后一个字符是 1。 你可以最多提 20 个问题，每次询问一个位置，交互器会回答你这个位置的字符。 最后你需要输出哪个位置 p 满足 S~p~≠S~p~。 数据范围：
- 2≤N≤2×10^5^
解题思路
经过分析，我们得到的几个关键信息：
- 最多可以问法官 20 个问题。
- s[1]=0,s[n]=1
==区域性查找，使用二分法==
看到 s[1]=0,s[n]=1，对于一个i得出结论：
- 如果 s[i]=0，那么 s[i] 右侧肯定有为 1 的元素。
- 如果 s[i]=1，那么 s[i] 左侧肯定有为 0 的元素。
==输出格式要注意！！！==
- 提问：
? x+换行 - 答案：
! x+换行
知识小卡片
==刷新缓冲区要用到fflush(stdout)==
详细描述可以到这里看看
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
int n, ans;
cin >> n;
int l = 1, r = n;
while(l <= r){
int mid = (l + r) / 2;
cout << "? " << mid;
cout << "\n";
fflush(stdout); // 一定要刷新缓冲区！！！
int x;
cin >> x;
if(x == 1){
ans = mid - 1;
r = mid - 1;
}
else {
l = mid + 1;
}
}
cout << "! " << ans;
cout << "\n";
fflush(stdout); // 一定要刷新缓冲区！！！
return 0;
}