专业网站建设公司怎么选,做公益网站的目的,黄山自驾游旅游攻略,房地产网站开发A.根据题意模拟即可
B.根据题意模拟即可
C.直接用map 进行dp即可
D.用前缀和进行模拟#xff0c;用map统计前缀和#xff0c;每次计算当前前缀和-k的个数就是以当前点为右端点答案。
E - Σ[k0..10^100]floor(X#xff0f;10^k) (atcoder.jp) #xff08;1#xff09;…A.根据题意模拟即可
B.根据题意模拟即可
C.直接用map 进行dp即可
D.用前缀和进行模拟用map统计前缀和每次计算当前前缀和-k的个数就是以当前点为右端点答案。
E - Σ[k0..10^100]floor(X10^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 pairint,int
#define fi first
#define se second
#define vi vectorint
#define vl vectorll
#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 pairint,int
#define fi first
#define se second
#define vi vectorint
#define vl vectorll
#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 {vectorint 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];
vectorPII e[N];
vectorint 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] ;}}queueint 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 pairint,int
#define fi first
#define se second
#define vi vectorint
#define vl vectorll
#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)的曼哈顿距离等价于新坐标系上xy,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 pairint,int
#define fi first
#define se second
#define vi vectorint
#define vl vectorll
#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;
vectorint 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()
{vectorPII 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;
}
