CF1451
Subtract or Divide
显然 如果为偶数 那么我们将它变到 \(2\) 再 \(-1\) 即可
如果为奇数 我们先 \(-1\) 再转化为偶数的情况即可
对于 \(n\le 3\) 进行特判
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inl inline
#define eb emplace_back
#define mid (l+r>>1)
#define getchar() cin.get()
#define print(x) cout<<#x<<'='<<x<<endl
const int N = 5e5 + 5;
const int inf = 0x3f3f3f3f;
int read()
{
int f = 1 , x = 0;
char ch = getchar();
while ( !isdigit(ch) ) { if ( ch == '-' ) f = -1; ch = getchar(); }
while ( isdigit(ch) ) { x = ( x << 1 ) + ( x << 3 ) + ( ch ^ 48 ); ch = getchar(); }
return x * f;
}
int n;
signed main ()
{
ios::sync_with_stdio(false);
cin.tie(0) , cout.tie(0);
int T = read();
while ( T -- )
{
n = read();
if ( n == 1 ) cout << 0 << endl;
else if ( n == 2 ) cout << 1 << endl;
else if ( n == 3 ) cout << 2 << endl;
else if ( n % 2 ) cout << 3 << endl;
else cout << 2 << endl;
}
return 0;
}
Non-Substring Subsequence
直接移动 \(l\) 指针和 \(r\) 指针去匹配 如果 \(l\) 左移或者 \(r\) 右移能相等 那么是合法的
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inl inline
#define eb emplace_back
#define mid (l+r>>1)
#define getchar() cin.get()
#define print(x) cout<<#x<<'='<<x<<endl
const int N = 5e5 + 5;
const int inf = 0x3f3f3f3f;
int read()
{
int f = 1 , x = 0;
char ch = getchar();
while ( !isdigit(ch) ) { if ( ch == '-' ) f = -1; ch = getchar(); }
while ( isdigit(ch) ) { x = ( x << 1 ) + ( x << 3 ) + ( ch ^ 48 ); ch = getchar(); }
return x * f;
}
int n , q;
string s;
signed main ()
{
ios::sync_with_stdio(false);
cin.tie(0) , cout.tie(0);
int T = read();
while ( T -- )
{
n = read() , q = read();
cin >> s , s = " " + s;
for ( int i = 1 ; i <= q ; i ++ )
{
int l = read() , r = read();
int flag = 0;
for ( int j = 1 ; j < l ; j ++ ) if ( s[l] == s[j] ) flag = 1;
for ( int j = r + 1 ; j <= n ; j ++ ) if ( s[r] == s[j] ) flag = 1;
cout << ( flag ? "YES" : "NO" ) << endl;
}
}
return 0;
}
String Equality
显然 因为我们可以随机交换字符位置 那么我们只用关注 \(ab\) 串中每一种字符的个数 开一个桶记录即可
然后我们可以从前向后推字符个数 如果 \(a\) 中该字符比 \(b\) 中多 且符合操作条件 那么我们将这些字符提升到下一位进行比较
注意 合法的操作条件是区间长度 \(\bmod k=0\) 而不是 \(\ge k\)
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inl inline
#define eb emplace_back
#define mid (l+r>>1)
#define getchar() cin.get()
#define print(x) cout<<#x<<'='<<x<<endl
const int N = 2e2 + 5;
const int inf = 0x3f3f3f3f;
int read()
{
int f = 1 , x = 0;
char ch = getchar();
while ( !isdigit(ch) ) { if ( ch == '-' ) f = -1; ch = getchar(); }
while ( isdigit(ch) ) { x = ( x << 1 ) + ( x << 3 ) + ( ch ^ 48 ); ch = getchar(); }
return x * f;
}
int n , k , cnta[N] , cntb[N];
char ch;
signed main ()
{
ios::sync_with_stdio(false);
cin.tie(0) , cout.tie(0);
int T = read();
while ( T -- )
{
memset ( cnta , 0 , sizeof cnta );
memset ( cntb , 0 , sizeof cntb );
n = read() , k = read();
for ( int i = 1 ; i <= n ; i ++ ) cin >> ch , cnta[ch] ++;
for ( int i = 1 ; i <= n ; i ++ ) cin >> ch , cntb[ch] ++;
int flag = 1;
for ( int i = 'a' ; i <= 'z' ; i ++ )
{
if ( cnta[i] >= cntb[i] && ( cnta[i] - cntb[i] ) % k == 0 ) cnta[i+1] += cnta[i] - cntb[i];
else { flag = 0; break; }
}
cout << ( flag ? "Yes" : "No" ) << endl;
}
return 0;
}
Circle Game
不止 \(*1700\) 罢 虽然代码难度很小
注意到先手一定可以将对手控制在 \(y=x+k\) 或 \(y=x-k\) 两条直线中
后手一定可以控制在 \(y=x\) 上 那么对于 \(y=x\) 上的最远合法点坐标(设为 \((nk,nk)\) 满足 \(\sqrt 2 nk\le d\))
如果 \(((n+1)k,nk)\) 也合法 那么 \((nk,nk)\) 就是一个先手必胜点 否则是必败点
因为如果在上述情况下 后手还能走动 那么一定走到了 \(((n+1)k,(n+1)k)\) 或者 \(((n+2)k,nk)\) 这两种情况都能说明 \(((n+1)k,(n+1)k)\) 是合法的 与 \(n\) 的最大性矛盾 所以结论得证
注意 \(long\ long\) 和 \(long\ double\)
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inl inline
#define eb emplace_back
#define mid (l+r>>1)
#define getchar() cin.get()
#define print(x) cout<<#x<<'='<<x<<endl
#define int long long
#define double long double
const int N = 2e2 + 5;
const int inf = 0x3f3f3f3f;
int read()
{
int f = 1 , x = 0;
char ch = getchar();
while ( !isdigit(ch) ) { if ( ch == '-' ) f = -1; ch = getchar(); }
while ( isdigit(ch) ) { x = ( x << 1 ) + ( x << 3 ) + ( ch ^ 48 ); ch = getchar(); }
return x * f;
}
int d , k;
signed main ()
{
ios::sync_with_stdio(false);
cin.tie(0) , cout.tie(0);
int T = read();
while ( T -- )
{
d = read() , k = read();
int n = (double)d/k*sqrtl(0.5);
if ( k * k * ( 2 * n * n + 2 * n + 1 ) <= d * d ) cout << "Ashish" << endl;
else cout << "Utkarsh" << endl;
}
return 0;
}
Bitwise Queries (Hard Version) && Bitwise Queries (Easy Version)
容易想到先用 \(n-1\) 次询问来问出所有的 \(a_1\oplus a_i\) 此时我们只需要知道 \(a_1\) 就能知道整个数组了
此时还剩两步操作 看到题中的 \(n\) 个数都在 \([0,n-1]\) 之间 那么我们可以分情况讨论
-
所有数都不重复
序列即为 \([0,n-1]\) 的排列 那么一定存在一个 \(a_1\oplus a_i=1\) 和一个 \(a_1\oplus a_j=n-2\)
此时 \(a_1\) 和 \(a_i\) 只有最后一位不一样 \(a_1\) 和 \(a_j\) 只有最后一位一样 那么或起来就可以得出整个数了
-
有两个数重复
那么一定异或值为 \(0\) 只需要与一下就行了
这样是 \(n\) 次操作
#include <bits/stdc++.h> using namespace std; #define inl inline #define eb emplace_back #define mid (l+r>>1) #define getchar() cin.get() #define print(x) cout<<#x<<'='<<x<<endl const int N = (1<<16) + 5; const int inf = 0x3f3f3f3f; int read() { int f = 1 , x = 0; char ch = getchar(); while ( !isdigit(ch) ) { if ( ch == '-' ) f = -1; ch = getchar(); } while ( isdigit(ch) ) { x = ( x << 1 ) + ( x << 3 ) + ( ch ^ 48 ); ch = getchar(); } return x * f; } int n , xr[N] , cnt[N] , pos = -1 , fi; int askxor ( int i , int j ) { cout << "XOR " << i << ' ' << j << endl; return read(); } int askand ( int i , int j ) { cout << "AND " << i << ' ' << j << endl; return read(); } vector<int> vec; signed main () { ios::sync_with_stdio(false); cin.tie(0) , cout.tie(0); n = read(); cnt[0] = 1; for ( int i = 2 ; i <= n ; i ++ ) cnt[xr[i]=askxor(1,i)] ++; for ( int i = 0 ; i < n ; i ++ ) if ( cnt[i] > 1 ) pos = i; if ( pos != -1 ) { for ( int i = 2 ; i <= n ; i ++ ) if ( xr[i] == pos ) vec.eb(i); fi = askand ( vec.size() == 1 ? 1 : *vec.begin() , vec.back() ) ^ pos; cout << "! " << fi << ' '; for ( int i = 2 ; i <= n ; i ++ ) cout << ( fi ^ xr[i] ) << ' '; } else { int ans1 , ans2; for ( int i = 2 ; i <= n ; i ++ ) { if ( xr[i] == 1 ) ans1 = i; if ( xr[i] == n - 2 ) ans2 = i; } fi = askand ( 1 , ans1 ) | askand ( 1 , ans2 ); cout << "! " << fi << ' '; for ( int i = 2 ; i <= n ; i ++ ) cout << ( fi ^ xr[i] ) << ' '; } return 0; }