AtCoder Beginner Contest 233 (A-Ex)

A.根据题意模拟即可

B.根据题意模拟即可

C.直接用map 进行dp即可

D.用前缀和进行模拟，用map统计前缀和，每次计算当前前缀和-k的个数就是以当前点为右端点答案。

E - Σ[k=0..10^100]floor(X／10^k) (atcoder.jp)

        （1）题意

        （2）思路

                手动推一下这个东西就会发现，其实每一位上的贡献等于这一位后面的所有数加起来，因此做一个后缀和即可。

        （3）代码

#include <bits/stdc++.h>
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define PII pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
const int N = 5e5 + 10;
ll Ans[N],suf[N];
void solve()
{string x;cin >> x;reverse(all(x));for(int i = sz(x) - 1;i >= 0;i --) suf[i] = suf[i + 1] + (x[i] - '0');for(int i = 0;i < sz(x);i ++) {Ans[i] = suf[i]; }    for(int i = 0;i < 500001;i ++) {Ans[i + 1] += Ans[i] / 10;Ans[i] %= 10;}int r = 500001;while(Ans[r] == 0) r --;while(r >= 0) cout << Ans[r --];
}
int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int T = 1;// cin >> T;while(T --) solve();return 0;
}

F - Swap and Sort (atcoder.jp)

        （1）题意

                有一个排列P，给出M组交换关系，第i组swap(Pai,Pbi)，问是否有可能可以使P不降。

        （2）思路

                首先，若i和P[i]不在一个连通块，则一定不会交换成功，然后考虑如何交换，对于度数为1的点说明我们此时交换掉他并且不会影响后继，因此满足拓扑排序，那么我们直接根据拓扑排序进行交换即可。

        （3）代码

#include <bits/stdc++.h>
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define PII pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
struct DSU {vector<int> f,siz;int n;DSU(int _n) {n = _n;f.resize(n + 1);siz.resize(n + 1,1);iota(f.begin(),f.end(),0);}inline int find(int x) {if(x == f[x]) return x;return f[x] = find(f[x]);}inline bool same(int x,int y) {x = find(x),y = find(y);return x == y;}inline void merge(int x,int y) {if(same(x,y)) return ;x = find(x),y = find(y);siz[y] += siz[x];f[x] = y;}//目前连通块个数inline int connect() {int res = 0;for(int i = 1;i <= n;i ++) {res += (i == find(i));}return res;}//求某一个联通块得大小inline int count(int x) {x = find(x);return siz[x];}
};
int p[N],deg[N];
vector<PII> e[N];
vector<int> ans;
inline bool dfs(int u,int f,int tar)
{if(u == tar) return true;for(auto [v,id]: e[u]) {if(v == f) continue;if(dfs(v,u,tar)) {swap(p[u],p[v]);ans.pb(id);return true;}}return false;
}
void solve()
{int n;cin >> n;rep(i,1,n) cin >> p[i];DSU dsu(n);int m;cin >> m;rep(i,1,m) {int u,v;cin >> u >> v;if(!dsu.same(u,v)) {dsu.merge(u,v);e[u].pb({v,i});e[v].pb({u,i});deg[u] ++,deg[v] ++;}}queue<int> q;rep(i,1,n) {if(!dsu.same(i,p[i])) {cout << -1 << '\n';return;}if(deg[i] == 1) q.push(i);}while(!q.empty()) {int v = q.front();q.pop();int tar = 0;for(int i = 1;i <= n;i ++) {if(p[i] == v) {tar = i;break;}}if(!dfs(v,0,tar)) {cout << -1 << '\n';return;}for(auto [u,id]: e[v]) {if(-- deg[u] == 1) q.push(u);}}cout << sz(ans) << '\n';for(auto x : ans) cout << x << ' ';
}
int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int T = 1;// cin >> T;while(T --) solve();return 0;
}

G - Strongest Takahashi (atcoder.jp)

        （1）题意

                给你一个N*N的矩形，里面#代表的是障碍，.不是障碍，你每次可以选择一个D*D的矩形把里面的障碍清除掉会花费D，问你把N*N的障碍全部清除掉的最小花费是多少。

        （2）思路

                很明显的一个思路是，这个可以分治进行dp，考虑dp[l1][r1][l2][r2]表示消除[l1-l2][r1-r2]这个矩形的最小花费，我们每一次可以枚举横着切下去还是竖着切下去就行，或者整个是正方形也可以直接清除，取个最小花费即可。

        （3）代码

#include <bits/stdc++.h>
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define PII pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
const int N = 55;
int dp[N][N][N][N],s[N][N];
string mp[N];
const int inf = 0x3f3f3f3f;
int get(int x1,int y1,int x2,int y2)
{return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
}
inline int dfs(int x1,int y1,int x2,int y2)
{if(dp[x1][y1][x2][y2] != -1) return dp[x1][y1][x2][y2];if(get(x1,y1,x2,y2) == 0) return dp[x1][y1][x2][y2] = 0;int mi = inf;for(int i = x1 + 1;i <= x2;i ++) {mi = min(mi,dfs(x1,y1,i - 1,y2) + dfs(i,y1,x2,y2));}for(int i = y1 + 1;i <= y2;i ++) {mi = min(mi,dfs(x1,y1,x2,i - 1) + dfs(x1,i,x2,y2));}if(x2 - x1 == y2 - y1) mi = min(mi,x2 - x1 + 1);return dp[x1][y1][x2][y2] = mi;
}
void solve()
{int n;cin >> n;memset(dp,-1,sizeof(dp));rep(i,1,n) {cin >> mp[i];mp[i] = " " + mp[i];rep(j,1,n) s[i][j] = s[i - 1][j] + s[i][j - 1] + (mp[i][j] == '#') - s[i - 1][j - 1];}cout << dfs(1,1,n,n);
}
int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int T = 1;// cin >> T;while(T --) solve();return 0;
}

Ex - Manhattan Christmas Tree (atcoder.jp)

        （1）题意

                二维平面上有N棵圣诞树，第i棵位于[xi,yi]，要回答一下Q个问题，第i个问题是，以曼哈顿距离为单位，(ai,bi)和距离该点最近的Ki棵圣诞树之间的距离是多少？

        （2）思路

                考虑曼哈顿距离不好进行计算，因此转换成切比雪夫距离，源坐标系上(x,y)的曼哈顿距离等价于新坐标系上（x+y,x-y)的切比雪夫距离，（补充：源坐标系上(x,y)的切比雪夫距离等价于新坐标系上（,)的曼哈顿距离）看着切比雪夫距离，我们很容易想到直接二分距离，问题转变这个矩形平面内有多少点，也就是二维数点问题，因为点不是很稠密，我们考虑直接动态开点二维树状数组。

        （3）代码

#include <bits/stdc++.h>
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define PII pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
const int N = 5e5 + 10;
vector<int> ver[N << 1];
inline int lowbit(int x)
{return x & (-x);
}
inline void add(int x,int y)
{x += N,y += N;if(!y) y = 1;while(y < 2 * N) {ver[y].pb(x);y += lowbit(y);}
}
inline int get(int y,int x1,int x2)
{int Ans = 0;y += N,x1 += N,x2 += N;if(y >= 2 * N) y = 2 * N - 1;while(y > 0) {Ans += upper_bound(all(ver[y]),x2) - lower_bound(all(ver[y]),x1);y -= lowbit(y);}return Ans;
}
inline int query(int x1,int y1,int x2,int y2)
{return get(y2,x1,x2) - get(y1 - 1,x1,x2);
}
void solve()
{vector<PII> point;int n;cin >> n;rep(i,1,n) {int x,y;cin >> x >> y;point.pb({x + y,x - y});}sort(all(point));for(auto [x,y]: point) add(x,y);int q;cin >> q;while(q --) {int x,y,k;cin >> x >> y >> k;int z = x;x = z + y,y = z - y;int l = 0,r = N;while(l <= r) {int m = (l + r) >> 1;if(query(x - m,y - m,x + m,y + m) < k) l = m + 1;else r = m - 1;}cout << l << '\n';}
}
int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int T = 1;// cin >> T;while(T --) solve();return 0;
}