2024 ICPC National Invitational Collegiate Programming Contest, Wuhan Site
I. Cyclic Apple Strings
题意：给定一个01字符串，每次操作可以将这个字符串向左循环移动任意次数，求让这个字符串变成有序的需要最少几次操作
思路：每次只能减少最右边的不和有边界相邻的一个1的长块，每次删去最右边的即可
void solve(){
string s;
cin >> s;
int ans = 0, idx = s.size() - 1;
while(idx >= 0 && s[idx] == '1') idx --;
for(idx; idx >= 0; idx --){
if(s[idx] == '1' && s[idx + 1] == '0') ans ++;
}
cout << ans << '\n';
}
K. Party Games
题意：给定 n 个整数从左到右排成一列，每次可以从两端拿走其中一个数字，如果数字被拿完了或者剩余的数字的异或和为0，则当前操作无法进行，就失败了
思路：打表发现 n % 4 == 0 || n % 4 == 1 的情况下 Fluttershy 必胜，否则必败
void solve(){
ll n;
cin >> n;
n %= 4;
if(n == 1 || n == 0) cout << "Fluttershy\n";
else cout << "Pinkie Pie\n";
}
B. Countless Me
题意：给定一个数组，每个数组的值可以随便分配，求最后的最小或运算的和
思路：从高位往低位贪心即可，如果在当前位的后面放满而且不够，那么放在当前位是最好的选择，注意这里的位数不要太大
void solve(){
ll n, x, sum = 0;
cin >> n;
for(int i = 1; i <= n; i ++){
cin >> x;
sum += x;
}
ll ans = 0;
for(int i = 30; i >= 0; i --){
if(sum > ((1ll << i) - 1) * n){
ll num = min(n, sum / (1ll << i));
sum -= num * (1ll << i);
ans += 1ll << i;
}
}
cout << ans << '\n';
}
F. Custom-Made Clothes
题意：给定一个n * n 的矩阵，矩阵的每个点大于等于它左边的和上边的点（如果存在），每次可以查询一个点的数字是不是小于等于给定的询问值，在50000次查询中得出第k大的数字
思路：看50000次查询能猜到复杂度应该是2nlogn级别，二分答案，每次查询从左下角开始，如果小于等于mid，往上移动，否则把这一列上面的数字的个数全部加上，否则左移，每次查询的次数不超过2*n，总计2nlogn次查询得出答案
int n, k;
int ask(int x, int y, int z){
cout << "? " << x << ' ' << y << ' ' << z << endl;
int ans;
cin >> ans;
return ans;
}
bool check(int x){
int sum = 0;
int a = n, b = 1;
while(a >= 1 && b <= n){
int ans = ask(a, b, x);
if(ans == 1){
sum += a;
b ++;
}
else{
a --;
}
}
if(sum >= k) return true;
else return false;
}
void solve(){
cin >> n >> k;
k = n * n - k + 1;
int l = 1, r = n * n;
while(l < r){
int mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
cout << "! " << l << endl;
}
pending。。。。。。
标签：Invitational,题意,idx,Contest,int,mid,查询,Wuhan,ans From： https://www.cnblogs.com/RosmontisL/p/18183336