[Codeforces Round 904 (Div. 2)](https://codeforces.com/contest/1894)
A. Simple Design
暴力就行了 1e9跑不满的
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
void solve(){
int x,k;
cin>>x>>k;
for(int i=x;i<=2e9;i++){
int y=i;
int sum=0;
while(y){
sum+=y%10;
y/=10;
}
if(sum%k==0&&sum>=k){
cout<<i<<endl;
return;
}
}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;
cin>>T;
while(T--) solve();
return 0;
}
B. Haunted House
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 1e5 + 10;
int re[N],pr[N];
void solve(){
int n;
string s;
cin>>n>>s;
reverse(s.begin(),s.end());
deque<int> idx;
for(int i=0;i<s.size();i++)
if(s[i]=='0')idx.push_back(i);
if(idx.empty()){
for(int i=0;i<s.size();i++)
cout<<-1<<" ";
cout<<endl;
return;
}
int ans=0;
for(int i=0;i<s.size();i++){
if(s[i]=='0'){
idx.pop_front();
cout<<ans<<" ";
}else{
if(idx.empty()){
for(int j=i;j<s.size();j++)
cout<<-1<<" ";
cout<<endl;
return;
}else{
ans += idx[0] - i;
s[idx[0]] = '1';
idx.pop_front();
cout<<ans<<" ";
}
}
}
cout<<endl;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;
cin>>T;
while(T--) solve();
return 0;
}
C. Medium Design
有个结论: 最小值一定在1处或者在m处。
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 2e5 + 10;
int n,m;
int pre[N],rev[N];
void solve(){
vector<int> p;
cin>>n>>m;
p.push_back(1);
p.push_back(m);
memset(pre,0,sizeof pre);
memset(rev,0,sizeof rev);
vector<pair<int,int>> x1(n);
for(auto &[l,r]:x1){
cin>>l>>r;
p.push_back(l);
p.push_back(r);
}
sort(p.begin(),p.end());
// cout<<endl;
// for(auto u:p) cout<<u<<" ";
// cout<<endl;
int idx=lower_bound(p.begin(),p.end(),m)-p.begin()+1;
for(auto &[l,r]:x1){
l=lower_bound(p.begin(),p.end(),l)-p.begin()+1;
r=lower_bound(p.begin(),p.end(),r)-p.begin()+1;
//cout<<l<<" "<<r<<endl;
}
for(auto [l,r]:x1){
if(l>1){
pre[l]++;
pre[r+1]--;
}
if(r<idx){
rev[l]++;
rev[r+1]--;
}
}
for(int i=1;i<=idx;i++){
pre[i] += pre[i-1];
rev[i] += rev[i-1];
}
int ans1=*max_element(pre+1,pre+1+idx);
int ans2=*max_element(rev+1,rev+1+idx);
cout<< max(ans1,ans2) <<endl;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;
cin>>T;
while(T--) solve();
return 0;
}
D. Counting Rhyme
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 1e6 + 10;
int a[N] , cnt[N];
int f[N]; //fi:gcd恰好为i的对数
bool vis[N];
int n;
void solve(){
cin>>n;
for(int i=0;i<=n;i++){
vis[i]=false;
f[i]=0;
cnt[i]=0;
a[i]=0;
}
int cx=0;
for(int i=1;i<=n;i++){
cin>>a[i];
cnt[a[i]]++;
cx = max(cx , a[i]);
}
for(int i=1;i<=cx;i++)
for(int j=2*i;j<=cx;j+=i)
cnt[i] += cnt[j];
for(int i=cx;i>0;i--){
f[i] = cnt[i]*(cnt[i]-1)/2;
for(int j=2*i;j<=cx;j+=i)
f[i] -= f[j];
}
for(int i=1;i<=cx;i++)
for(int j=a[i];j<=cx;j+=a[i]) vis[j]=true;
long long ans=0;
for(int i=1;i<=cx;i++)
if(!vis[i]) ans+=f[i];
cout<<ans<<endl;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T=1;
cin>>T;
while(T--) solve();
return 0;
}
标签:pre,904,int,Codeforces,long,--,solve,Div,define
From: https://www.cnblogs.com/zfxyyy/p/17891395.html