Atcoder Beginner Contest 269

A - Anyway Takahashi

题目太水了，一年级小朋友都可以做

#include<bits/stdc++.h>
using namespace std;
int main(){int a,b,c,d;cin>>a>>b>>c>>d;cout<<(a+b)*(c-d)<<endl;cout<<"Takahashi";
}

B - Rectangle Detection

遍历这十个字符串，不断地更新左边界，右边界的大小即可，取最小的左边界和最大的右边界

#include<bits/stdc++.h>
using namespace std;
char s[20][20];
int main(){for(int i=1;i<=10;i++) cin>>s[i]+1;int minl=11,maxl=-1;int minr=11,maxr=-1;for(int i=1;i<=10;i++){for(int j=1;j<=10;j++){if(s[i][j]=='#'){minl=min(minl,i);maxl=max(maxl,i);minr=min(minr,j);maxr=max(maxr,j);}}}cout<<minl<<' '<<maxl<<endl;cout<<minr<<' '<<maxr<<endl;
}

C - Submask

位运算 构造

这道题让我们求原来的那个数含有1的位置的子集，联想到快速幂，可以将原数中含有1的位置保存下来，然后新建一个vector保存答案。

接下来遍历保存1位置的那个数组，将答案数组中的每一个数的二进制那一位上的数从0变成1，再将产生的新数保存在答案数组里。

#include<bits/stdc++.h>using namespace std;int main(){long long x;cin >> x;vector<long long> res={0};for(int d=0;d<60;d++){if(x&(1ll<<d)){int sz=res.size();for(int i=0;i<sz;i++){res.push_back(res[i]|(1ll<<d));}}}sort(res.begin(),res.end());for(auto &nx : res){cout << nx << "\n";}return 0;
}

D - Do use hexagon grid

一看到可以往六个方向进行扩展，咦，搜索的感觉来了，从涂黑的格子出发，将它所能到达的黑色格子都标记成白色，直到没有黑色的格子可以到达。

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
map<PII,bool>ma;
int x[1500],y[1500];
int dx[10]={-1,-1,0,0,1,1};
int dy[10]={-1,0,-1,1,0,1};
void dfs(int xi,int yi){if(ma[make_pair(xi,yi)]==true) return;ma[make_pair(xi,yi)]=true;for(int i=0;i<6;i++){int xx=xi+dx[i],yy=yi+dy[i];if(ma.count(make_pair(xx,yy))) dfs(xx,yy);}
}
int main(){int n;cin>>n;for(int i=0;i<n;i++){int xi,yi;cin>>xi>>yi;x[i]=xi;y[i]=yi;ma[make_pair(xi,yi)]=false;}int ans=0;int siz=ma.size();for(int i=0;i<n;i++){if(ma[make_pair(x[i],y[i])]==false){dfs(x[i],y[i]);ans++;}}cout<<ans;
}

E - Last Rook

交互题

F - Numbered Checker

二维前缀和，矩形容斥

首先将问题转化成从左上角$(1,1)$到右下角$(x,y)$的和，看数据范围，显然将每一个格子都算出来是不现实的。看原来的式子，$(i-1)\times m+j$发现行与列之间没有任何关系，那么就可以将行与列分开来算

将每个$(x,y)$都算出来之后利用容斥原理，计算和。即$f(b,d)-f(b,c)-f(a,d)+f(a,c)$

#include <bits/stdc++.h>
using namespace std;
const int maxn = 4 * 1e5 + 10, mod = 998244353;
const int half = 499122177;
const int maxn_mp = 1005;
typedef long long ll;
typedef pair<int, int> pii;
ll n, m;
int ap(int l, int d, int cnt) {int r = (l + (d % mod) * (cnt - 1) % mod) % mod;return (l + r) % mod * cnt % mod * half % mod;
}
int area(int a, int b) {
//	if (a <= 0 || b <= 0) return 0;int s1 = ap(1, 1, b);int ans1 = ap(s1, b * m, a);int ans2 = 0;if (a % 2) {ans2 += mod - (b / 2);}if (b % 2) {ans2 += mod - (a / 2) * m % mod;}if (a % 2 == 1 && b % 2 == 1) {ans2 += (a - 1) * m + b;}ans2 %= mod;return (ans1 + ans2) * half % mod;
}
signed main() {//freopen("w.ans", "w", stdout);ios::sync_with_stdio(false);cin.tie(0);//int tt; cin >> tt; while(tt--) solve(); cin >> n >> m;int q;cin >> q;while(q--) {int now = 0, a, b, c, d; cin >> a >> b >> c >> d;a--, c--;int s1 = area(b, d);int s2 = area(a, c);int s3 = area(b, c);int s4 = area(a, d);cout << ((s1 - s3 - s4 + s2) % mod + mod) % mod << endl;}return 0;
} 

G - Reversible Cards 2

可以转化成01背包问题，将该模型转化成一个容量为s的背包，s为最开始正面朝上数的和，有$N$个物品，每个物品的体积为$b_i-a_i$，代价为1，请你求出如何用最小的代价来填满背包。但看数据范围,01背包的时间复杂度肯定超时的，所以可以盲猜，总有$b_i-a_i$相等的情况吧，具体的证明可以参照原题解。这样就把$01$背包转化成了多重背包。

#include<bits/stdc++.h>
using namespace std;
int main(){int n,m;cin>>n>>m;map<int,int>mp;int s=0;for(int i=1;i<=n;i++){int a,b;cin>>a>>b;++mp[b-a];s+=a;}const int INF=0x3f3f3f3f;vector<int>dp(m+1,INF);dp[s]=0;for(auto it : mp){int d=it.first;int c=it.second;	if(d==0) continue;int x=1;while(c){x=min(x,c);if(d>0){for(int i=m;i>=d*x;i--){dp[i]=min(dp[i],dp[i-d*x]+x);}}else{for(int i=0;i-d*x<=m;i++){dp[i]=min(dp[i],dp[i-d*x]+x);}}c=c-x;x=x*2;}}for(int i=0;i<=m;i++){if(dp[i]==INF) cout<<-1<<endl;else cout<<dp[i]<<endl;}
}