Codeforces Round 1016 (Div. 3)¶
2025-04-09 这把打得有点烂
比赛链接: https://codeforces.com/contest/2093
先简单贴下代码吧，前面的题感觉没啥要记的。明天再去看看FG。
A¶
B¶
for _ in range(int(input())):
n = input()
# n.sort()
cnt = 0
# x/len 是答案
#
ans = 1000
res = len(n)-1
for i in range(len(n)):
if n[i]=='0':
cnt+=1
else:
ans = int(n[i])/(cnt+1)
cnt = 0
for i in range(len(n)):
if n[i]=='0':
cnt+=1
elif int(n[i])/(cnt+1)==ans:
res = min(res,len(n)-(cnt+1))
print(res)
C¶
def is_prime(x):
if x==1:
return False
i=2
while i*i<=x:
if x%i==0:
return False
i+=1
return True
for _ in range(int(input())):
x,k=map(int,input().split())
if k!=1:
if x==1 and k==2:
print("YES")
else:
print("NO")
else:
if is_prime(x):
print("YES")
else:
print("NO")
D¶
给我整好长时间才写出来，索性直接开unsigned long long 了，其实思路是对的。
#define int unsigned long long
using namespace std;
int n,q;
char ch;
int dfs1(int sz,int val,int x,int y)
{
if(x==1&&y==1) return val;
int tt=sz/2;
if(x>sz/2&&y>sz/2)
return dfs1(sz>>1,val+(sz*sz/4),x-tt,y-tt);
else if(x>sz/2)
return dfs1(sz>>1,val+2*(sz*sz/4),x-tt,y);
else if(y>sz/2)
return dfs1(sz>>1,val+3*(sz*sz/4),x,y-tt);
return dfs1(sz>>1,val,x,y);
}
pair<int,int>dfs2(int sz,int val,int x,int y,int find_val)
{
if(val==find_val) return make_pair(x,y);
int tt=sz*sz/4;
if(find_val>=3*tt+val)
return dfs2(sz>>1,val+3*tt,x,y+sz/2,find_val);
else if(find_val>=2*tt+val)
return dfs2(sz>>1,val+2*tt,x+sz/2,y,find_val);
else if(find_val>=tt+val)
return dfs2(sz>>1,val+tt,x+sz/2,y+sz/2,find_val);
return dfs2(sz>>1,val,x,y,find_val);
}
void solve()
{
cin>>n>>q;
while(q--){
cin>>ch>>ch;
if(ch=='>'){
int x,y;
cin>>x>>y;
assert(dfs1(1LL<<n,1,x,y)<=(1LL<<(2*n)));
cout<<dfs1(1LL<<n,1,x,y)<<'\n';
}
else{
int d;
cin>>d;
auto [l,r]=dfs2(1LL<<n,1,1,1,d);
assert(l<=(1<<n)&&r<=(1<<n));
assert(dfs1(1LL<<n,1,l,r)==d);
cout<<l<<" "<<r<<'\n';
}
}
}
E¶
就直接二分就行，这个还挺基础的。
for _ in range(int(input())):
n,k = map(int,input().split())
a = list(map(int,input().split()))
lo = 0
hi = n+1
def check(x):
st = set()
cnt=0
for i in range(n):
if a[i]<x:
st.add(a[i])
if len(st)==x:
cnt+=1
st.clear()
return cnt>=k
while lo<hi-1:
mid = (lo+hi)>>1
if check(mid):
lo=mid
else:
hi=mid
print(lo)
F¶
服了，什么水题，虽然感觉难度应该不会太难，但是这也太简单了吧，感觉是不是该 *1300 。
for _ in range(int(input())):
n , m = map(int,input().split())
a = list(input().split())
b = [[]] * m
cnt = [0]*n
for i in range(m):
b[i] = list(input().split())
for j in range(n):
if b[i][j]==a[j]:
cnt[j]+=1
ans = 1000000000
for i in range(m):
now = n
for j in range(n):
if b[i][j]!=a[j]:
# print(b[i][j],a[j])
if cnt[j]>=1:
now+=2
else:
break
else:
ans=min(ans,now)
if ans==1000000000:
print(-1)
else:
print(ans)
G¶
需要用 trie 以及观察以下二进制。
我们用 trie 可以查出一个数字和前面的数字的最大的异或结果，但是这里是看是否能和前面异或大于等于 \(k\) ，且这个长度要是最短的。
我们可以二进制从高位往低位看，一直让当前异或出来的值的前缀和 \(k\) 的前缀是相等的，那么当 \(k\) 取 \(0\) 的位，我们如果能异或得到 \(1\) ，就一定会大于 \(k\) 。所以我们只需要存一下每一位有 \(1\) 的最大的下标，\(trie_{cur,x}\) 实际上每一个值都是不同的，可以用这个来记状态。
void ChatGptDeepSeek() // Date: 2025-04-10
{ // Time: 20:26:45
int n, k;
cin >> n >> k;
vector<vi> trie(n * 31, vi(2));
vi p(n * 32);
int tot = 0, ans = n + 1;
auto Insert = [&](int Val, int idx)
{
int cur = 0;
for (int i = 30; i >= 0; i--)
{
int x = Val >> i & 1;
if (trie[cur][x] == 0)
trie[cur][x] = ++tot;
cur = trie[cur][x];
p[cur] = idx;
}
};
auto Find = [&](int Val)
{
int cur = 0, now = 0, L = -1;
for (int i = 30; i >= 0; i--)
{
int x = Val >> i & 1;
int y = k >> i & 1;
if (y)
{
if (!trie[cur][x ^ 1])
return L;
cur = trie[cur][x ^ 1];
}
else
{
if (trie[cur][x ^ 1])
cmax(L, p[trie[cur][x ^ 1]]);
if (trie[cur][x] == 0)
return L;
cur = trie[cur][x];
}
}
cmax(L,p[cur]);
return L;
};
for (int i = 1; i <= n; i++)
{
int x;
cin >> x;
int L=Find(x);
if(L>0) ans=min(ans,i-L+1);
Insert(x, i);
}
if (k == 0)
cout << "1\n";
else if (ans == n + 1)
cout << "-1\n";
else
cout << ans << '\n';
}