Codeforces Round 1013 (Div. 3)¶
2025-03-25
赛时没打。。虽然unrated，但是以后能打的尽量都打吧，赛后打其实更耽误时间，状态还不一定好，花的时间可能更长，早做完早省事。
比赛链接: https://codeforces.com/contest/2091
A¶
for _ in range(int(input())):
a=[0]*10
# print(a)
n = int(input())
b=list(map(int,input().split()))
for i in range(n):
a[b[i]]+=1
if a[0]>=3 and a[1]>=1 and a[2]>=2 and a[3]>=1 and a[5]>=1:
print(i+1)
break
else:
print(0)
B¶
for _ in range(int(input())):
n,x=map(int,input().split())
a=list(map(int,input().split()))
a.sort(reverse=True)
ans=0
lst=-1
for i in range(n):
if (i-lst)*a[i]>=x:
lst=i
ans+=1
print(ans)
C¶
直接guess就行，偶数都构造不出来。奇数猜一下。
void ChatGptDeepSeek()
{
int n;
cin>>n;
if(n%2==0){
cout<<"-1\n";
return;
}
for(int i=1;i<=n;i+=2)
cout<<i<<" ";
for(int i=2;i<=n;i+=2)
cout<<i<<" ";
cout<<'\n';
}
D¶
二分，注意剩下的长度可以填别的。不要爆int。
void ChatGptDeepSeek()
{
int n, m, k;
cin >> n >> m >> k;
int lo = 0, hi = m + 1;
auto check = [&](int len)
{
int num = (m + 1) / (len + 1) * len;
int rest = (m + 1) % (len + 1);
return 1LL * (num + max(0, rest - 1)) * n >= k;
};
while (lo < hi - 1)
{
int mid = (lo + hi) >> 1;
if (check(mid))
hi = mid;
else
lo = mid;
}
cout << hi << '\n';
}
E¶
\(lcm(a,b)=\frac{ab}{gcd(a,b)}\)
所以 设 $g=gcd(a,b) $ ， \(a\) 和 \(b\) 可以表示成 \(xg\) 和 \(yg\) 的形式，其中 \(x\) 和 \(y\) 互质。
也就是说 \(lcm(a,b)=\frac{ab}{g}\) , \(\frac{lcm(a,b)}{gcd(a,b)}=\frac{ab}{g^2}=xy\) 若 \(xy\) 为素数，则 \(x\) 和 \(y\) 必然一个是素数，另一个是 \(1\) 。所以两个数字是 \(g\) 和 \(gx\) ，且 \(x\) 是素数，所以我们只需要枚举每一个素数，找它们有多少个倍数即可。
找素数需要学一下筛法，不然你判断一个素数就需要 $\sqrt{V} $ 的复杂度。 这个筛素数的还是比较好理解的，而且CF感觉挺常见的。
constexpr int N = 1e7;
int minp[N + 1];
/*
ab/gcd/gcd
x*gcd*gcd*y /gcd*gcd
也就是说 y是一个质数
x是1
*/
void ChatGptDeepSeek()
{
int n;
cin >> n;
long long ans = 0;
for (int i = 2; i <= n; i++)
{
if (minp[i] == i)
{
ans += n / i;
}
}
cout << ans << '\n';
}
/*
2 , 1 2, 2 4,
3 , 1 3
4 , 1 4
5 , 1 5
*/
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
for (int i = 2; i <= N; i++)
{
if (minp[i])
continue;
minp[i] = i;
if (i * i > N)
continue;
if(1LL*i*i>N) continue;
for (int j = i * i; j <= N; j += i)
minp[j] = i;
}
int T = 1;
cin >> T;
while (T--)
ChatGptDeepSeek();
return 0;
}
F¶
题解里学的 DP ，其实我本来题都没太读明白，原来只能去上一行或同一行，不能跳好几次。当然感觉这个DP还是很复杂的。。看题解都写了一会。
using ll = long long;
constexpr int mod = 998244353;
ll dp[2002][2002][2], pre[2002][2002][2];
void ChatGptDeepSeek()
{
int n, m, d;
cin >> n >> m >> d;
// vector<vector<int>> dp(n + 1, vector<int>(m + 1));
vector<vector<char>> s(n + 1, vector<char>(m + 1));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> s[i][j];
/*
dp[i][j][0] i j
*/
for (int i = 1; i <= m; i++)
{
pre[n][i][0] = dp[n][i][0] = s[n][i] == 'X' ? 1 : 0;
pre[n][i][0] = (pre[n][i - 1][0] + pre[n][i][0]) % mod;
dp[n][i][1] = 0;
}
auto get0 = [&](int i, int j, int di)
{
return (pre[i][min(m, j + di)][0] - pre[i][max(0, j - di - 1)][0] + mod) % mod;
};
auto get1 = [&](int i, int j, int di)
{
return (pre[i][min(m, j + di)][1] - pre[i][max(0, j - di - 1)][1] + mod) % mod;
};
for (int j = 1; j <= m; j++)
{
pre[n][j][1] = pre[n][j - 1][1];
if (s[n][j] != 'X')
continue;
dp[n][j][1] = (get0(n, j, d) - dp[n][j][0] + mod) % mod;
pre[n][j][1] = (pre[n][j][1] + dp[n][j][1]) % mod;
}
int d1 = d;
while (d1 * d1 + 1 > d * d)
d1--;
// cerr << d1 << '\n';
for (int i = n - 1; i >= 1; i--)
{
for (int j = 1; j <= m; j++)
{
/* x*x+1*1<=d*d */
/* (d-1)*(d-1)+1<=d*d */
pre[i][j][0] = pre[i][j - 1][0];
if (s[i][j] != 'X')
{
dp[i][j][0] = 0;
continue;
}
dp[i][j][0] = (get1(i + 1, j, d1) + get0(i + 1, j, d1)) % mod;
pre[i][j][0] = (pre[i][j][0] + dp[i][j][0]) % mod;
}
for (int j = 1; j <= m; j++)
{
pre[i][j][1] = pre[i][j - 1][1];
if (s[i][j] != 'X')
{
dp[i][j][1] = 0;
continue;
}
dp[i][j][1] = (get0(i, j, d) - dp[i][j][0] + mod) % mod;
pre[i][j][1] = (pre[i][j][1] + dp[i][j][1]) % mod;
}
}
cout << (pre[1][m][0] + pre[1][m][1]) % mod << '\n';
}