B - Gold Medal
statements
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve(){
int n,k;
cin>>n>>k;
vector<int>a(n);
int ans=0;
for(int i=0;i<n;i++){
cin>>a[i];
ans+=a[i]/k;
a[i]=a[i]%k;
}
sort(a.begin(),a.end(),greater<int>());
int m;
cin>>m;
for(int i=0;i<n;i++){
if(m+a[i]>=k){
m-=k-a[i];
ans++;
}
}
ans+=m/k;
cout<<ans<<"\n";
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--){
solve();
}
return 0;
}
G - Be Positive
statements
#include <iostream>
#include <bits/stdc++.h>
#define int long long
const int N=1e6+5;
using namespace std;
int a[N],b[N];
bool vis[N];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int sum=0;
for(int i=0;i<N;i++){
a[i]=i;
b[i]=i;
}
for(int i=0;i<N-1;i++){
sum=(sum^a[i]);
if(sum==0){
swap(b[i],b[i+1]);
vis[i+1]=true;
}
}
int t;
cin>>t;
while(t--){
int n;
cin>>n;
if(vis[n]==true){
cout<<"impossible\n";
}
else {
for(int i=0;i<n;i++)cout<<b[i]<<" ";
cout<<"\n";
}
}
return 0;
}
I - Left Shifting 2
statements
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10;
bool vis[N];
int n;
int cal(string s){
int res=0;
int l=0,r=0;
while(r<n){
r=l;
while(r+1<n&&s[l]==s[r+1]) r++;
if(s[l]==s[r]){
res+=(r-l+1)/2;
}
l=r+1;
}
return res;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin>>t;
while(t--){
string s;
cin>>s;
n=s.length();
int pos=-1;
if(s[0]==s[n-1]){
for(int i=0;i<n;i++)
if(s[i]==s[0]) pos=i;
else break;
if(pos==n-1){
cout<<n/2<<'\n';
continue ;
}
}
string tmp;
tmp=s.substr(pos+1,n)+s.substr(0,pos+1);
int ans=cal(tmp);
int l=0,r=0;
int flag=0;
while(r<n){
r=l;
while(r+1<n&&tmp[l]==tmp[r+1]) r++;
if(tmp[l]==tmp[r]){
int len=r-l+1;
if(len%2==0) flag=1;
}
l=r+1;
}
cout<<ans-flag<<'\n';
}
return 0;
}
A - Two-star Contest
statements
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct node{
int fi, se, s, id;
node(): fi(0), se(0), s(0), id(0) {}
};
void solve(){
int n,m,k;
cin>>n>>m>>k;
vector<vector<int>> p(n+1, vector<int>(m+1, 0));
vector<node> info(n+1);
vector<int> idd(n+1,0);
for(int i=1;i<=n;i++){
cin>>info[i].s;
info[i].fi = 0;
info[i].se = 0;
for(int j=1;j<=m;j++){
cin>>p[i][j];
if(p[i][j] != -1) info[i].fi += p[i][j];
else info[i].se++;
}
info[i].id = i;
}
sort(info.begin()+1, info.end(), [&](const node &a, const node &b){
return a.s > b.s;
});
for(int i=1;i<=n;i++) idd[info[i].id] = i;
const long long INF = (long long)9e18;
long long prev_min = INF; // 所有下一组值都必须 < prev_min
vector<int> ans(n+1, 0);
int i = 1;
while(i <= n){
int j = i;
while(j <= n && info[j].s == info[i].s) j++;
// group is [i, j-1]
// For each member compute its max, and assign limit = min(max, prev_min-1)
long long group_min_assigned = INF;
// First pass: check feasibility
for(int t = i; t < j; t++){
long long maxv = info[t].fi + info[t].se * (long long)k;
long long limit = min(maxv, prev_min - 1);
if(limit < info[t].fi){
cout << "No\n";
return;
}
}
// Second pass: actually assign
for(int t = i; t < j; t++){
long long maxv = info[t].fi + info[t].se * (long long)k;
long long limit = min(maxv, prev_min - 1);
ans[info[t].id] = (int)limit;
if(limit < group_min_assigned) group_min_assigned = limit;
}
// update prev_min for next lower-s groups
prev_min = group_min_assigned;
i = j;
}
// 填回缺失值（按原行顺序）
for(int r = 1; r <= n; r++){
int idx = idd[r]; // 在排序后的 info 中的索引
for(int c = 1; c <= m; c++){
if(p[r][c] == -1){
if(info[idx].fi == ans[r]){
p[r][c] = 0;
} else if(info[idx].fi + k <= ans[r]){
info[idx].fi += k;
p[r][c] = k;
} else {
p[r][c] = ans[r] - info[idx].fi;
info[idx].fi = ans[r];
}
}
}
}
cout << "Yes\n";
for(int r = 1; r <= n; r++){
for(int c = 1; c <= m; c++){
cout << p[r][c] << (c==m?'\n':' ');
}
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin>>t;
while(t--) solve();
return 0;
}
参考代码
#include <bits/stdc++.h>
using i64 = long long;
void Solve() {
int n, m;
i64 K;
std::cin >> n >> m >> K;
std::vector<int> c(n);
std::vector<i64> s(n);
std::map<int, std::vector<int>> adj;
std::vector a(n, std::vector<int>(m));
for (int i = 0; i < n; ++i) {
int x;
std::cin >> x;
adj[x].push_back(i);
int cnt = 0;
i64 sum = 0;
for (int j = 0; j < m; ++j) {
std::cin >> a[i][j];
if (a[i][j] == -1) {
++cnt;
} else {
sum += a[i][j];
}
}
c[i] = cnt;
s[i] = sum;
}
i64 last = 0;
for (auto [_, vec] : adj) {
i64 Min = last, Max = 1e18;
for (int i : vec) {
Min = std::max(Min, s[i]);
Max = std::min(Max, s[i] + c[i] * K);
}
if (Max < last) {
std::cout << "No" << "\n";
return;
}
for (int i : vec) {
i64 rest = std::min(s[i] + c[i] * K, Min) - s[i];
for (int j = 0; j < m; ++j) {
if (a[i][j] == -1) {
i64 d = std::min(rest, K);
a[i][j] = d;
rest -= d;
}
}
}
last = Min + 1;
// std::cerr << Min << ' ' << Max << '\n';
}
std::cout << "Yes" << "\n";
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
std::cout << a[i][j] << ' ';
}
std::cout << '\n';
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
std::cin >> t;
for (int ti = 1; ti <= t; ++ti) {
// std::cerr << "Solve : " << ti << '\n';
Solve();
}
return 0;
}
E - Relearn through Review
statements
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin>>t;
while(t--){
int n,k;
cin>>n>>k;
vector<int> a(n+2,0);
vector<int> g(n+2,0);
vector<int> suf(n+2,0);
for(int i=1;i<=n;i++){
cin>>a[i];
g[i]=__gcd(g[i-1],a[i]);
}
for(int i=n;i>=1;i--) suf[i]=__gcd(suf[i+1],a[i]);
int ans=g[n];
for(int i=1;i<=n;i++){
if(g[i]!=g[i-1]){
int gc=g[i-1];
for(int j=i;j<=n;j++){
gc=__gcd(gc,a[j]+k);
ans=max(ans,__gcd(gc,suf[j+1]));
}
}
}
cout<<ans<<'\n';
}
return 0;
}
H - Subarray
statements
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 998244353;
const int G = 3;
ll mod_pow(ll a, ll b){
ll r = 1;
while(b){
if(b & 1) r = r * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return r;
}
ll mod_inv(ll a){ return mod_pow(a, MOD-2); }
void ntt(vector<ll>& a, bool invert){
int n = (int)a.size();
// bit reversal
for (int i = 1, j = 0; i < n; i++){
int bit = n >> 1;
for (; j & bit; bit >>= 1) j ^= bit;
j ^= bit;
if (i < j) swap(a[i], a[j]);
}
for (int len = 2; len <= n; len <<= 1){
ll wlen = mod_pow(G, (MOD - 1) / len);
if (invert) wlen = mod_inv(wlen);
for (int i = 0; i < n; i += len){
ll w = 1;
for (int j = 0; j < len/2; j++){
ll u = a[i+j];
ll v = a[i+j+len/2] * w % MOD;
a[i+j] = (u + v) % MOD;
a[i+j+len/2] = (u - v + MOD) % MOD;
w = w * wlen % MOD;
}
}
}
if (invert){
ll inv_n = mod_inv(n);
for (ll &x : a) x = x * inv_n % MOD;
}
}
vector<ll> multiply(const vector<ll>& A, const vector<ll>& B){
if (A.empty() || B.empty()) return {};
vector<ll> fa(A.begin(), A.end()), fb(B.begin(), B.end());
int n = 1;
while (n < (int)(A.size() + B.size())) n <<= 1;
fa.resize(n); fb.resize(n);
ntt(fa, false); ntt(fb, false);
for (int i = 0; i < n; i++) fa[i] = fa[i] * fb[i] % MOD;
ntt(fa, true);
return fa;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
if (!(cin >> T)) return 0;
while (T--){
int n;
cin >> n;
vector<ll> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
// prev greater (strict) and next greater (strict)
vector<int> left(n), right(n);
stack<int> st;
for (int i = 0; i < n; i++){
while (!st.empty() && a[st.top()] <= a[i]) st.pop();
left[i] = st.empty() ? -1 : st.top();
st.push(i);
}
while (!st.empty()) st.pop();
for (int i = n-1; i >= 0; i--){
while (!st.empty() && a[st.top()] <= a[i]) st.pop();
right[i] = st.empty() ? n : st.top();
st.push(i);
}
// group by (left, right, value)
// key: tuple<int,int,ll>
unordered_map<long long, vector<int>> groups;
groups.reserve(n * 2);
// encode triple into 64-bit key: L (20 bits) | R (20 bits) | hashed value low 24 bits
// careful about collisions; a safer map<tuple,..> is slower; using unordered_map with a combined key is acceptable here.
// We'll use a robust encoding assuming n <= 2e5 and values fit in 32-bit.
auto make_key = [&](int L, int R, ll v)->long long{
// shift L and R to non-negative
long long Lp = (long long)(L + 1); // L in [-1..n-1] -> [0..n]
long long Rp = (long long)R; // R in [0..n]
// Use 21 bits for Lp and 21 bits for Rp (supports n up to ~2e6). Remaining bits for value hashed.
long long key = (Lp << 42) ^ (Rp << 21) ^ ( (long long)( (v ^ (v >> 32)) & ((1<<21)-1) ) );
return key;
};
for (int i = 0; i < n; i++){
long long key = make_key(left[i], right[i], a[i]);
groups[key].push_back(i);
}
vector<ll> ans(n+1, 0);
for (auto &kv : groups){
vector<int>& pos = kv.second;
if (pos.empty()) continue;
sort(pos.begin(), pos.end());
int m = (int) pos.size(); // occurrences count
// build t of length m+1, t0 = pos[0] - left[pos[0]] , t_j = pos[j] - pos[j-1], t_m = right[pos[m-1]] - pos[m-1]
vector<ll> t;
t.reserve(m+1);
int first = pos[0];
int Lg = left[first];
t.push_back( (ll)first - (ll)Lg ); // = g0+1
for (int j = 1; j < m; j++){
t.push_back( (ll)pos[j] - (ll)pos[j-1] ); // g_j + 1
}
int last = pos.back();
int Rg = right[last];
t.push_back( (ll)Rg - (ll)last ); // = g_m + 1
// convolution with reversed t
vector<ll> treg = t;
reverse(treg.begin(), treg.end());
vector<ll> conv = multiply(t, treg);
// conv length >= 2*(m+1)-1
// For k = 1..m, contribution is C_{m - k}
// Here m_occ = m, conv index = m - k
for (int k = 1; k <= m; k++){
int idx = m - k;
if (0 <= idx && idx < (int)conv.size()){
ans[k] = (ans[k] + conv[idx]) % MOD;
}
}
}
int res=0;
for (int k = 1; k <= n; k++){
res+=ans[k]*ans[k]%MOD*k%MOD;
res%=MOD;
}
cout << res<< '\n';
}
return 0;
}
