Codeforces Round 920 (Div. 3)
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 5e5 + 10;
void solve()
{
map<int,int> x;
map<int,int> y;
for(int i=0;i<4;i++)
{
int a,b;
cin >> a >> b;
x[a]++;
y[b]++;
}
vector<int> path1,path2;
for(auto [x,y]:x) path1.push_back(x);
for(auto [x,y]:y) path2.push_back(x);
cout << abs(path1[1]-path1[0])*abs(path2[0]-path2[1])<<endl;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T = 1;
cin >> T;
while(T--) solve();
return 0;
}
B - Arranging Cats
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 5e5 + 10;
void solve()
{
int n;
string a,b;
cin >> n;
cin >> a >> b;
int ans = 0;
int cnt1=0,cnt2=0;
for(int i=0;i<n;i++)
{
if(a[i]=='1'&&b[i]=='0') cnt1++;
else if(a[i]=='0'&&b[i]=='1') cnt2++;
}
cout << max(cnt1,cnt2) <<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 - Sending Messages
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 5e5 + 10;
int a[N];
void solve()
{
int n,f,c,b;
cin >> n >> f >> c >>b;
for(int i=1;i<=n;i++) cin >> a[i];
a[0] = 0;
for(int i=1;i<=n;i++){
int cnt = min((a[i]-a[i-1])*c,b);
f -= cnt;
//cout << cnt << " " <<f<<endl;
if(f<=0){
cout<<"NO"<<endl;
return;
}
}
cout <<"YES"<<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 - Very Different Array
好丑陋的code
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 2e5 + 10;
int b[N];
int c[N];
void solve()
{
int n,m;
cin >> n >> m;
deque<int> a;
for(int i=1;i<=n;i++)
{
int x;
cin >> x;
a.push_back(x);
}
for(int i=1;i<=m;i++) cin>>b[i];
sort(b+1,b+1+m);
sort(a.begin(),a.end());
int l = 1, r = m;
int ans = 0;
while(a.size())
{
int x,y,z,q;
x = abs(a.front()-b[l]);
y = abs(a.front()-b[r]);
z = abs(a.back() -b[l]);
q = abs(a.back() -b[r]);
int qq=max({x,y,z,q});
if(x==qq&&x==y){
ans +=x ;
r--;
a.pop_front();
}else if(z==qq&&z==q){
ans += z;
l++;
a.pop_back();
}else if(x==qq&&y!=x){
ans += x;
l++;
a.pop_front();
}else if(y==qq&&x!=y){
ans += y;
r--;
a.pop_front();
}else if(z==qq&&z!=q){
ans +=z;
l++;
a.pop_back();
}else if(q==qq&&z!=q){
ans += q;
r--;
a.pop_back();
}
}
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;
}
E - Eat the Chip
- 一个移动一次一定会往上移动一行 一个移动一定会往下移动一行
- 所以谁能赢跟行差的奇偶有关
- 赢不了的那个一定会往两边跑争取不输
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
void solve()
{
int h,w,x1,y1,x2,y2;
cin >> h >> w >> x1 >> y1 >> x2 >> y2;
if(x1>=x2)
{
cout << "Draw" <<endl;
return;
}
int len = x2 - x1 - 1;
if(len&1)
{
int cnt = len/2 + 1;
int l1 = max(1ll,y1-cnt);
int r1 = min(w,y1+cnt);
int l2 = max(1ll,y2-cnt);
int r2 = min(w,y2+cnt);
if(l2<=l1&&r2>=r1)
{
cout << "Bob" <<endl;
return;
}
else
{
cout << "Draw" <<endl;
}
}
else
{
int cnt = len/2;
int l1 = max(1ll,y2-cnt);
int r1 = min(w,y2+cnt);
cnt++;
int l2 = max(1ll,y1-cnt);
int r2 = min(w,y1+cnt);
if(l2<=l1&&r2>=r1)
{
cout << "Alice" <<endl;
return;
}
else
{
cout << "Draw" <<endl;
}
}
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T = 1;
cin >> T;
while(T--) solve();
return 0;
}
F. Sum of Progression
又是被分治腐乳的一天
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 1e5 + 10;
void solve()
{
int n,q;
cin >> n >> q;
vector<int> a(n+1);
for(int i=1;i<=n;i++) cin >>a[i];
vector<vector<int>> pre(n*2,vector<int>(220));
vector<vector<int>> sum(n*2,vector<int>(220));
for(int d=1;d<=200;d++)
{
for(int i=1;i<=n;i++)
{
if(i-d<=0)
{
pre[i][d]=a[i];
sum[i][d]=a[i];
}
else
{
int k=i/d;
if(i%d) k++;
pre[i][d]=pre[i-d][d] + a[i]*k;
sum[i][d]=sum[i-d][d] + a[i];
}
}
}
while(q--)
{
int s,d,k;
cin >> s >> d >> k;
int ans = 0;
if(d>200)
{
for(int i=0;i<k;i++)
ans += a[s+i*d]*(i+1);
}
else
{
if(s-d<0)
{
ans = pre[s+(k-1)*d][d];
}
else
{
ans = pre[s+(k-1)*d][d] - pre[s-d][d];
int z = s/d-1;
if(s%d) z++;
ans -= (sum[s+(k-1)*d][d]-sum[s-d][d])*z;
}
}
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;
}