day1-day4
因为感觉多写一点对自己有一点点难度的题，会帮助很大。所以决定试一下。比如每天写3道cf rating在*1600-*1800的题目，看看一段时间之后能不能稳定蓝名水平不要掉到青。。。
然后有时候可能也会写洛谷的绿色难度的题，大致也是最低cf *1600的题。说白了其实大部分都是看题解的，甚至可能看题没看一会就看题解。只能说我试一下吧，也许是骗自己，也许是有帮助，总比什么都不做好。
day1 2月19日¶
CF2022C *1800¶
这个 DP 太牛。。。
每次分割完区域之后，末尾只有几种状态:
X表示已经被选出来，$ .$ 表示没有被选。
因为如果放了一个长度为3的，那么底下也一定得放一个。所以状态其实可以看成只有这3种。然后进行DP，看每一种状态的票数是多少。
我刚才还在想，它怎么保证答案一定是合法的划分呢？
其实因为可以倒着看的，最后是全部填满了，所以逆着推回去一定会是全部填满的。
void solve()
{
/*
dp0 dp1 dp2
X. XX XX
XX X. XX
*/
int n;
cin>>n;
string s[2];
cin>>s[0]>>s[1];
s[0]=" "+s[0];
s[1]=" "+s[1];
auto check1=[&](int i){
return ((s[0][i+1]=='A')+(s[1][i+1]=='A')+(s[1][i+2]=='A'))>=2;
};
auto check2=[&](int i){
return (s[0][i+1]=='A')+(s[1][i+1]=='A')+(s[0][i+2]=='A')>=2;
};
auto check3=[&](int i){
int res=0;
assert(i+3<=n);
if((s[0][i+1]=='A')+(s[0][i+2]=='A')+(s[0][i+3]=='A')>=2) res++;
if((s[1][i+1]=='A')+(s[1][i+2]=='A')+(s[1][i+3]=='A')>=2) res++;
return res;
};
vector<vi> dp(n+1,vi(3));
for(int i=1;i<=n;i++){
if(i+1<=n){
cmax(dp[i+1][0],dp[i-1][2]+check1(i-1));
cmax(dp[i+1][1],dp[i-1][2]+check2(i-1));
cmax(dp[i+1][2],dp[i][0]+((s[0][i]=='A')+(s[0][i+1]=='A')+(s[1][i+1]=='A')>=2));
cmax(dp[i+1][2],dp[i][1]+((s[1][i]=='A')+(s[0][i+1]=='A')+(s[1][i+1]=='A')>=2));
}
if(i+3<=n){
cmax(dp[i+3][0],dp[i][0]+((s[0][i]=='A')+(s[0][i+1]=='A')+(s[0][i+2]=='A')>=2)+((s[1][i+1]=='A')+(s[1][i+2]=='A')+(s[1][i+3]=='A')>=2));
cmax(dp[i+3][1],dp[i][1]+((s[1][i]=='A')+(s[1][i+1]=='A')+(s[1][i+2]=='A')>=2)+((s[0][i+1]=='A')+(s[0][i+2]=='A')+(s[0][i+3]=='A')>=2));
}
if(i+2<=n){
cmax(dp[i+2][2],dp[i-1][2]+check3(i-1));
}
}
// for(int i=1;i<=n;i++)
// cerr<<dp[i][0]<<" "<<dp[i][1]<<" "<<dp[i][2]<<" \n";
cout<<dp[n][2]<<'\n';
}
CF1949I *1800¶
这是之前咱们一起打的那一场，只写了一题。
那个圆盘的题。。。
看了题解感觉就好有道理，而且不是很难想。
说白了目前还是得多抄题解才能进步。。。
因为半径之和要严格减小，那些不与其他圆盘相切的，很显然可以直接减小就行。如果有若干个相切的挨在一起，如果有一个圆盘半径减小，那么和它相邻的一定要增加。我们只需要检查有没有合法的方案，且增大减小的数量不同，则可以使得总的半径减小。
可以把相切的连边建图，这样会有若干个连通块。检查有没有可以减小半径的。题解说好像这样黑白染色的就是二分图，有空看看这个概念。
啊。我服了，一个 continue 的位置放错了导致 WA 了半小时才发现，一直 RE ，幸好能看错在第几个测试点，RE 很多时候可能是因为内存暴了，递归没有结束之类的。
void solve()
{
int n;
cin>>n;
vi x(n+1),y(n+1),r(n+1);
for(int i=1;i<=n;i++)
cin>>x[i]>>y[i]>>r[i];
vector<vi>adj(n+1,vi());
auto calc=[&](int x){
return 1ll*x*x;
};
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++){
if(calc(x[i]-x[j])+calc(y[i]-y[j])==calc(r[i]+r[j])){
adj[i].push_back(j);
adj[j].push_back(i);
}
}
vi s(n+1,-1);
for(int i=1;i<=n;i++){
if(s[i]!=-1) continue;
bool ok=true;
int x=0,y=0;
auto dfs=[&](auto &&self,int u)->void{
if(s[u]) x++;
else y++;
// cerr<<u<<'\n';
for(auto v:adj[u]){
if(s[v]!=-1){
if(s[v]==s[u]) ok=false;
continue;
}
s[v]=s[u]^1;
self(self,v);
}
};
s[i]=0;
dfs(dfs,i);
if(ok&&x!=y){
cout<<"YES\n";
return;
}
}
cout<<"NO\n";
}
CF1995C *1800¶
给一个数组 \(a\) ，每次可以选择一个 \(a_i\) 将其变为 \(a_i^2\) ，问最少需要多少次操作才能使其成为非递减数组。
直接乘肯定会爆。其实可以临时进行操作使得 \(a_i\) 刚好大于 \(a_{i-1}\) ，这样我们可以记录每个 \(a_i\) 需要操作多少次。
如果 \(a_i\) 先操作到刚好大于 \(a_{i-1}\) ，那么只需要加上 \(a_{i-1}\) 的操作次数就行。
记 \(f_i\) 为 \(a_i\) 需要操作的次数，如果 \(a_i\) 比 \(a_{i-1}\) 小，那么显然进行同样次数的操作是不够用的，所以我们需要先记录使得 \(a_i\) 刚好大于 \(a_{i-1}\) 的操作次数。若一开始就大于，就得把 \(a_{i-1}\) 增大到刚好小于 \(a_i\) 。
void solve()
{
int n;
cin>>n;
vl a(n+1);
for(int i=1;i<=n;i++)
cin>>a[i];
ll ans=0;
vl b(n+1);
for(int i=2;i<=n;i++){
if(a[i]==1&&a[i]<a[i-1]){
cout<<"-1\n";
return;
}
}
for(int i=2;i<=n;i++){
ll x=a[i],y=a[i-1];
while(x<y){
x*=x;
b[i]++;
}
while(y!=1&&y*y<=x){
y*=y;
b[i]--;
}
b[i]+=b[i-1];
cmax(b[i],0LL);
ans+=b[i];
}
cout<<ans<<'\n';
}
洛谷P3386 普及+/提高¶
二分图最大匹配问题。
每次看新的点能不能找到匹配的点。
void solve()
{
int n,m,e;
cin>>n>>m>>e;
vector<vi>adj(n+1,vi());
for(int i=1;i<=e;i++){
int u,v;
cin>>u>>v;
adj[u].push_back(v);
}
vector<int>match(m+1);
int ans=0;
for(int i=1;i<=n;i++){
vector<bool>sel(m+1);//记有没有被选过
auto dfs=[&](auto &&self,int u)->bool{
for(auto v:adj[u]){
if(!sel[v]){
sel[v]=true;
if(!match[v]||self(self,match[v])){
match[v]=u;
return true;
}
}
}
return false;
};
if(dfs(dfs,i))
ans++;
}
cout<<ans<<'\n';
}
day2 2月20日¶
CF1985H1 *1700¶
这题好简单，直接暴力就过了。
void solve()
{
int n,m;
cin>>n>>m;
vector<vector<char>>a(n+1,vector<char>(m+1));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
int tot=0,sum=0;
vector<vi>vis(n+1,vi(m+1));
vector<pii>dir{{0,1},{0,-1},{1,0},{-1,0}};
auto dfs=[&](auto &&self,int i,int j)->void{
// cerr<<i<<" "<<j<<'\n';
vis[i][j]=tot;
sum++;
for(auto [dx,dy]:dir){
int nx=dx+i,ny=dy+j;
if(nx<1||nx>n||ny<1||ny>m) continue;
if(a[nx][ny]=='#'&&!vis[nx][ny])
self(self,nx,ny);
}
};
vi cnt(n*m+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(a[i][j]=='#'&&!vis[i][j]){
// cerr<<i<<" "<<j<<'\n';
++tot,sum=0;
dfs(dfs,i,j);
cnt[tot]=sum;
}
}
// cerr<<tot<<'\n';
int ans=0;
for(int i=1;i<=n;i++){
int now=m;
set<int>st;
if(i-1>=1){
for(int j=1;j<=m;j++)
st.insert(vis[i-1][j]);
}
if(i+1<=n){
for(int j=1;j<=m;j++){
st.insert(vis[i+1][j]);
}
}
for(int j=1;j<=m;j++){
st.insert(vis[i][j]);
now-=(a[i][j]=='#');
}
for(auto x:st)
now+=cnt[x];
cmax(ans,now);
}
for(int i=1;i<=m;i++){
int now=n;
set<int>st;
if(i-1>=1){
for(int j=1;j<=n;j++)
st.insert(vis[j][i-1]);
}
if(i+1<=m){
for(int j=1;j<=n;j++){
st.insert(vis[j][i+1]);
}
}
for(int j=1;j<=n;j++){
st.insert(vis[j][i]);
now-=(a[j][i]=='#');
}
for(auto x:st)
now+=cnt[x];
cmax(ans,now);
}
cout<<ans<<'\n';
}
CF1930C *1700¶
这个没想到哈。
就是拿的顺序无所谓的，因为你并不是要优先拿大的。先拿后面的一样的。
直接先将 \(a_i+i\) 排序，然后顺着拿。因为并不是多集，所以重复的咱们一定是把他 -1 。
void solve()
{
int n;
cin >> n;
vi a(n + 1);
for (int i = 1; i <= n; i++)
cin >> a[i], a[i] += i;
sort(ALL(a), greater<>());
set<int> st;
st.insert(a[1]);
for (int i = 2; i <= n; i++) {
cmin(a[i],a[i-1]-1);
st.insert(a[i]);
}
for (auto it = st.rbegin(); it != st.rend(); it++)
cout << *it << ' ';
cout << '\n';
}
CF1923D *1800¶
唉唉，这个自己多看看说不定能想出来的。
二分，首先肯定有单调性。
其次只要某一段不全为同一个数字，那么肯定可以合成一个。
void solve()
{
int n;
cin >> n;
vi a(n + 1);
for (int i = 1; i <= n; i++)
cin >> a[i];
vi c(n + 1);
vl pre(n + 1);
for (int i = 1; i <= n; i++)
pre[i] = pre[i - 1] + a[i];
for (int i = 2; i <= n; i++)
c[i] = c[i - 1] + (a[i - 1] != a[i]);
for (int i = 1; i <= n; i++) {
int ans = n + 1;
if (a[i - 1] > a[i])
ans = 1;
if (i + 1 <= n && a[i + 1] > a[i])
ans = 1;
if (pre[i - 1] > a[i] && c[i - 1]) {
int lo = 0, hi = i;
while (lo < hi - 1) {
int mid = (lo + hi) >> 1;
if (pre[i - 1] - pre[mid - 1] > a[i] && c[i - 1] - c[mid])
lo = mid;
else
hi = mid;
}
cmin(ans, i - lo);
}
if (i != n && pre[n] - pre[i] > a[i] && c[n] - c[i + 1]) {
int lo = i, hi = n + 1;
while (lo < hi - 1) {
int mid = (lo + hi) >> 1;
// cerr<<mid<<" "<<pre[mid]-pre[i]<<'\n';
if (pre[mid] - pre[i] > a[i] && c[mid] - c[i + 1])
hi = mid;
else
lo = mid;
}
cmin(ans, hi - i);
}
if (ans == n + 1)
ans = -1;
cout << ans << " \n"[i == n];
}
}
day3 2月21 22日¶
这几天没咋写。。。
CF2044G1 *1700¶
因为有n个点n条边，每个人都有一个出度，且没有自环，所以一定会有环。环上的点是一直不会变的，所以需要等其他的点都变成0。所以我们需要找连到环上的最长的链。然后这个链上的点全变成0了之后，点的值就不会变了。直接DFS就行。
void solve()
{
int n;
cin >> n;
vi r(n + 1), a(n + 1, 1), de(n + 1);
a[0] = 0;
for (int i = 1; i <= n; i++) {
cin >> r[i];
de[r[i]]++;
}
/*
只有在环上的点是不会变的
否则就得找最长的链是多长
*/
vi t = de;
vector<bool> circle(n + 1);
vi L(n + 1);
auto topsort = [&]() {
queue<int> q;
for (int i = 1; i <= n; i++)
if (!de[i])
q.push(i);
while (!q.empty()) {
int x = q.front();
// cerr<<x<<'\n';
circle[x] = true;
q.pop();
// assert(x>=1&&x<=n);
if (!(--de[r[x]]))
q.push(r[x]);
}
// cerr<<sz(q)<<'\n';
while (!q.empty()) {
assert(q.front() >= 1 && q.front() <= n);
circle[q.front()] = true;
q.pop();
}
};
topsort();
int ans = 0;
for (int i = 1; i <= n; i++) {
if (!t[i]) {
auto dfs = [&](auto&& self, int u) {
// cerr<<u<<'\n';
// assert(len<=n);
// assert(u<=n);
if (!circle[u] || L[u])
return;
self(self, r[u]);
cmax(L[u], L[r[u]] + 1);
cmax(ans, L[u]);
};
dfs(dfs, i);
}
}
cout << ans + 2 << '\n';
}
用拓扑排序把不在环上的点给找出来，然后咱们可以只对不在环上的点进行DFS，而且可以只用对入度为0的点开始DFS，这样一定可以走到所有不在环上的点。
CF2044G2 *1900¶
和G1特别像，也挺简单的其实。。。
因为可以存在手上，然后也只有环上的点不会变。所以需要统计所有连在环上的点的子树的最大大小。
我自己写得有问题找了好久，因为我最开始写的是统计环上的点能到的点的数量。。。但实际上，一个点可能会连几个子树，这几个子树是同时减小的，所以要注意这一点。。。
void solve()
{
/*
因为不会丢了，n条边 一定会有环
那么必须保证每个环上每个点上的值一直相同
即同一环上每一个点连的点的数量要是相同的
。。。不对，唐了
每次只会给一个 所以无论如何环上是不会变的
*/
int n;
cin >> n;
vi r(n + 1), a(n + 1, 1), de(n + 1);
a[0] = 0;
for (int i = 1; i <= n; i++) {
cin >> r[i];
de[r[i]]++;
}
vi t = de;
vector<bool> circle(n + 1);
// vi L(n + 1);
auto topsort = [&]() {
queue<int> q;
for (int i = 1; i <= n; i++)
if (!de[i])
q.push(i);
while (!q.empty()) {
int x = q.front();
circle[x] = true;
q.pop();
if (!(--de[r[x]]))
q.push(r[x]);
}
};
topsort();
int ans = 0;
vi cnt(n + 1), f(n + 1);
for (int i = 1; i <= n; i++) {
if (!t[i]) {
auto dfs = [&](auto&& self, int u) -> void {
if (f[u])
return;
if (!circle[r[u]]) {
f[u] = u;
cnt[u] = 1;
return;
}
self(self, r[u]);
f[u] = f[r[u]];
cnt[f[u]]++;
// cerr << u<<" "<<f[u] << " " << cnt[f[u]] << '\n';
// assert(f[u]&&(f[u]!=u)&&(!circle[f[u]]));
cmax(ans, cnt[f[u]]);
};
dfs(dfs, i);
}
}
cmax(ans, *max_element(ALL(cnt)));
cout << ans + 2 << '\n';
}
CF2059C *1600¶
好简单的，，，只要用上一点点的观察能力。
赛时卡b好久，然后c没咋看了。恼。
void solve()
{
/*
第n-1次服务只能给a_n=1的
而n-2次服务只能给a_n=1 a_n-1=1的
因为要+2个数字等于2 所以只能那样
所以咱们就是要看全由1组成的列有多少个
*/
int n;
cin >> n;
vector<vi> a(n + 1, vi(n + 1));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> a[i][j];
// vi cnt(n + 1);
multiset<int> st;
for (int i = 1; i <= n; i++) {
int now = 0;
for (int j = n; j >= 1; j--) {
if (a[i][j] != 1)
break;
now++;
}
// cnt[now]++;
st.insert(now);
}
for (int i = 1; i < n; i++) {
if (*st.rbegin() < i) {
cout << i << '\n';
return;
}
st.erase(st.lower_bound(i));
}
cout << n << '\n';
}
因为 \(a_{i,j}\) 范围是 \([1,10^9]\) ，我们每次必须让一列变成0，那么我们倒数第二次服务的那一列，他的最后一个数字必须是1，不然我们不可能得到1了。我们下一个要得到的数字是2，但只能在倒数第二次操作之前用了，但是两个数字以上加起来是不可能等于2的，而两个数字加起来等于2也只有一种情况。
所以我们只有对后两个数字都为1的那一列操作才能得到1。
同理，我们要得到下一个值，只能是那一列后面的连续的1的个数大于这个值。
唉唉，感觉很多大概难度的题，多想一会就能出来的。就算想不出来，也会好很多。
day4 2月24日¶
CF1766D *1600¶
\(gcd(x,y)\) = \(gcd(x,y\%x)\)
这题里，我们知道 \(gcd(x+k,y+k)\) = \(gcd(x+k,y-x)\) ，所以如果 \(gcd(x+k,y+k)\ne 1\) ，那么 \(x+k\) 一定会是 \(y-x\) 的一个因子的倍数。但是直接枚举因子，复杂度很高，无法通过本题。
于是我看了题解才知道，只用枚举质因子，因为如果不是质因子，比如让 $x=(\lfloor\frac{x}{g}\rfloor+1) \cdot g $，如果 \(g\) 不是质数，那我们可以用 \(g\) 的因子，绝对不会情况更差。
筛质因子，我们可以先预处理出每个数字的最小质因子。知道最小质因子之后可以一直除最小质因子，然后就可以分解出质因子。在预处理完后，筛质因子复杂度为 \(\log k\) 。
用埃氏筛法的复杂度为 \(n\log\log n\) ，欧拉筛的复杂度为 \(n\) 。
constexpr int N = 1e7 + 5;
int mind[N + 5];
void init()
{
for (int i = 1; i <= N; i++)
mind[i] = i;
for (int i = 2; i * i <= N; i++) {
if (mind[i] != i)
continue;
for (int j = i * i; j <= N; j += i)
cmin(mind[j], i);
}
}
vi get_primes(int x)
{
vi res;
while (x > 1) {
res.push_back(mind[x]);
while (x % res.back() == 0)
x /= res.back();
}
return res;
}
void solve()
{
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
if (y == x + 1) {
cout << "-1\n";
continue;
}
if (__gcd(x, y) != 1) {
cout << "0\n";
continue;
}
int z = y - x;
int ans = INF;
auto calc = [&](int t) {
return (x / t + 1) * t;
};
for (auto v : get_primes(z)) {
cmin(ans, calc(v) - x);
}
cout << ans << '\n';
}
}
洛谷P10814 普及+/提高¶
确实是一个很典的题，我记得网络赛还是哪个区域赛也有个差不多的。。。
我们用线段树和树状数组查询小于等于x的数字的数量是比较容易的，但是如果要查询区间的，时间复杂度就会比较高。
可以离线处理，走到 \(l-1\) ，就先把对应的 \(ans\) 减去当前的小于 \(x\) 的数量，然后等走到 \(r\) 再加上当前的小于 \(x\) 的数量。
constexpr int N = 2e6;
struct Fenwick {
vector<int> b;
Fenwick()
{
// b.resize(N+1,0);
b = vector<int>(N + 1);
}
int lowbit(int x) { return (x) & (-x); }
void upd(int i, int x)
{
while (i <= N) {
// dbg(i);
b[i] += x;
i += lowbit(i);
}
}
int ask(int i)
{
int res = 0;
while (i) {
// cerr<<"ask: "<<i<<" "<<b[i]<<'\n';
res += b[i];
i -= lowbit(i);
}
// cerr<<"res: "<<res<<'\n';
return res;
}
int query(int l, int r)
{
return ask(r) - ask(l - 1);
}
};
void solve()
{
Fenwick C;
int n, m;
cin >> n >> m;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++)
cin >> a[i];
vector<array<int, 4>> q(m);
for (int i = 0; i < m; i++)
cin >> q[i][0] >> q[i][1] >> q[i][2], q[i][3] = i;
sort(q.begin(), q.end(), greater<>());
vector<vector<pair<int, int>>> adj(n + 1, vector<pair<int, int>>());
vector<int> ans(m);
for (int i = 1; i <= n; i++) {
// cerr<<"i: "<<i<<'\n';
while (!q.empty() && q.back()[0] == i) {
auto [x, y, z, j] = q.back();
// cerr<<"q: "<<z<<" "<<j<<'\n';
q.pop_back();
// dbg(adj);
// dbg(q);
ans[j] -= C.ask(z);
adj[y].push_back({ z, j });
}
// dbg("yuanshen");
// dbg(adj);
C.upd(a[i], 1);
for (auto [x, j] : adj[i]) {
// cerr<<" adj: "<<x<<" "<<j<<'\n';
ans[j] += C.ask(x);
}
}
for (auto x : ans)
cout << x << "\n";
// cout<<'\n';
}
CF2045M *1800¶
不是，这怎么也能是1800的题啊，写了就能对。。。虽然我WA了，没看数据感觉很难找出来。。。
没注意。。。不用 to_string 导致的。
void solve()
{
int r, c;
cin >> r >> c;
vector<string> s(r);
int all = 0;
for (int i = 0; i < r; i++) {
cin >> s[i];
for (auto x : s[i])
if (x == '\\' || x == '/')
all++;
}
// map<char, pair<int, int>> mp;
vector<pair<int, int>> mp(128);
mp['N'] = { 1, 0 }, mp['S'] = { -1, 0 };
mp['W'] = { 0, 1 }, mp['E'] = { 0, -1 };
// int cnt = 0;
set<pair<int, int>> st;
auto dfs = [&](auto&& self, int x, int y, char d) -> void {
if (x < 0 || x >= r || y < 0 || y >= c)
return;
if (s[x][y] == '/') {
// cnt++;
st.insert({ x, y });
if (d == 'N')
d = 'E';
else if (d == 'S')
d = 'W';
else if (d == 'W')
d = 'S';
else
d = 'N';
} else if (s[x][y] == '\\') {
// cnt++;
st.insert({ x, y });
if (d == 'N')
d = 'W';
else if (d == 'S')
d = 'E';
else if (d == 'W')
d = 'N';
else
d = 'S';
}
int nx = x + mp[d].first, ny = y + mp[d].second;
self(self, nx, ny, d);
};
vector<string> ans;
for (int _ = 0; _ < 2; _++) {
char d = (_ ? 'N' : 'S');
for (int i = 0; i < c; i++) {
// cnt = 0;
st.clear();
if (d == 'N')
dfs(dfs, 0, i, d);
else
dfs(dfs, r - 1, i, d);
// cerr<<cnt<<'\n';
if (st.size() == all) {
string tmp { d };
// tmp.push_back('1' + i);
tmp+=to_string(i+1);
ans.push_back(tmp);
}
}
}
for (int _ = 0; _ < 2; _++) {
char d = (_ ? 'W' : 'E');
for (int i = 0; i < r; i++) {
// cnt = 0;
st.clear();
if (d == 'W')
dfs(dfs, i, 0, d);
else
dfs(dfs, i, c - 1, d);
if (st.size() == all) {
string tmp { d };
// tmp.push_back('1' + i);
tmp+=to_string(i+1);
ans.push_back(tmp);
}
}
}
cout << ans.size() << '\n';
for (auto x : ans)
cout << x << ' ';
}
但是真的写了就能过啊，之前看过一眼这个题，看到这个图就不想写了。但是真写起来很简单，就按题意DFS就行。在洛谷估计要 建议评橙 了。好吧没有，是绿。开个玩笑
我要做的是板刷，那么就是不能管难还是简单，不管写起来难不难受，就顺着写，而且其实难度都差不多的，多思考，总会更接近答案的。
CF2045A *1700¶
这题更是简单，虽然还是花了三十多分钟，很慢了。
就是纯分类讨论+一点点贪心。。。
只要能耐心写，大概率能写出来的。
void solve()
{
string s;
cin >> s;
vector<int> cnt(26);
for (auto x : s)
cnt[x - 'A']++;
int vowels = cnt['A' - 'A'] + cnt['E' - 'A'] + cnt['I' - 'A'] + cnt['O' - 'A'] + cnt['U' - 'A'];
int consonants = s.size() - vowels;
if (vowels * 2 > consonants) {
// cerr << "1\n";
vowels = consonants / 2;
int ans = vowels * 3;
int rest = consonants % 2;
int x = cnt['N' - 'A'], y = cnt['G' - 'A'];
if (x > y)
swap(x, y);
// 最多只能多加x个
ans += min({ vowels * 2, x, rest });
cout << ans << '\n';
} else {
// 可能需要用y
int x = cnt['N' - 'A'], y = cnt['G' - 'A'], z = cnt['Y' - 'A'];
if (x > y)
swap(x, y);
if ((vowels + z) * 3 <= s.size()) {
// 肯定全拿
// cerr << "2\n";
int ans = (vowels + z) * 3;
int rest = s.size() - ans;
ans += min({ (vowels + z) * 2, x, rest });
cout << ans << '\n';
} else {
// 否则只能加一部分
// 直接拿成s.size()/3
vowels = s.size() / 3;
if (vowels * 3 == s.size()) {
// cerr << "3\n";
cout << s.size() << '\n';
} else {
// 否则继续之前的操作
// cerr << "4\n";
int ans = vowels * 3;
int rest = s.size() - ans;
int x = cnt['N' - 'A'], y = cnt['G' - 'A'];
if (x > y)
swap(x, y);
// 最多只能多加x个
ans += min({ vowels * 2, x, rest });
cout << ans << '\n';
}
}
}
}
也多亏样例给得算比较强的了，不然有些情况确实可能得多花点时间才能想到。。。
CF2039C2 *1800¶
当 \(y\le x\) 时，我们直接算就行了。
当 $y>x $ 时，\(x\oplus y\le x+y <2y\) ，所以 \(x\oplus y\) 不可能被 \(y\) 整除，只可能是 \(x\) 的倍数。
我们设 \(p=x\oplus y\) ，那么 \(y=p\oplus x\) ，我们需要 \(y\) 是小于等于 \(m\)。
\(p\) 是 \(x\) 的倍数，\(y\le p\oplus x\le p+x\le m\) ，所以 \(x\) 的 \(\lfloor\frac{m}{x}\rfloor-1\) 倍肯定都是能表示出来的，咱们只用判断 \(\lfloor\frac{m}{x}\rfloor\) 能不能达到。
不对，再判一下多一点能不能达到。为什么只用多判一个再多一倍？
\(x\oplus y \le x+y\) ，所以若 \(x\oplus y >m+x\) ，那么 \(y> m\) ，所以 \(p\le m+x\) ，所以不可能大于 \(\lfloor \frac{m}{x} \rfloor +1\) 倍。
void solve()
{
int x;
long long m;
cin>>x>>m;
long long ans=0;
for(int i=1;i<=min(m,1LL*x-1);i++){
if((i^x)%i==0)
ans++;
}
if(m<x){
cout<<ans<<'\n';
}else{
ans+=m/x-1;
if(((m/x*x)^x)<=m) ans++;
if(((m/x*x+x)^x)<=m) ans++;
cout<<ans<<'\n';
}
}
感觉是一道非常好的题目啊，之前记得哪一场区域赛还是啥，也有一个类似的。。。非常好的题目，感觉有必要收藏一下。
看了一下题解，但是这些是按我自己的理解推出来的。