Codeforces Round #675 (Div. 2)——F主席树待补?

A - Fence

把凑得那条边当成最长的边，如果a+b+c=d那么将会共线，只要稍微a+b+c大一点即可满足四边形。

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<queue> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int N=100010; const ll mod=998244353; int main() { IO; int T=1; cin>>T; while(T--) { ll a,b,c; cin>>a>>b>>c; cout<<a+b+c-1<<'\n'; } return 0; }

B - Nice Matrix

不难发现由于需要满足回文有以下关系： $a_{(i,j)}=a_{(n-i+1,j)}=a_{(i,m-j+1)}=a_{(n-i+1,m-j+1)}$ 单独考虑这四元组，需要找到$x$使得$$|x-a_{(i,j)}|+|x-a_{(n-i+1,j)}|+|x-a_{(i,m-j+1)}+|x-a_{(n-i+1,m-j+1)}|$$最小，只需要找中位数即可。

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<queue> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int N=110; const ll mod=998244353; ll a[N][N]; int n,m; ll tmp[5]; ll calc(ll a,ll b,ll c,ll d) { ll res=0; tmp[1]=a,tmp[2]=b,tmp[3]=c,tmp[4]=d; sort(tmp+1,tmp+1+4); ll mid=tmp[2]; return abs(a-mid)+abs(b-mid)+abs(c-mid)+abs(d-mid); } int main() { IO; int T=1; cin>>T; while(T--) { cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j]; ll res=0; int rmid=1+n>>1,cmid=1+m>>1; if(n&1) { for(int j=1;j<=cmid;j++) { ll mid=a[rmid][j]+a[rmid][m-j+1]>>1; res+=abs(a[rmid][j]-mid)+abs(a[rmid][m-j+1]-mid); } rmid--; } if(m&1) { for(int i=1;i<=rmid;i++) { ll mid=a[i][cmid]+a[n-i+1][cmid]>>1; res+=abs(a[i][cmid]-mid)+abs(a[n-i+1][cmid]-mid); } cmid--; } for(int i=1;i<=rmid;i++) for(int j=1;j<=cmid;j++) res+=calc(a[i][j],a[i][m-j+1],a[n-i+1][j],a[n-i+1][m-j+1]); cout<<res<<'\n'; } return 0; }

C - Bargain

单独考虑每位的对答案的贡献： 某位想要有贡献那么首先该位不能被删除，因而选择删除的子串只可能有两种情况：①该位前面②该位后面 不妨设第$i$位的数是$d$（$i$从高位） 如果去掉的子串在该位前面，则贡献为：$\frac{i(i-1)}{2}d\times 10^{n-i}$ 如果去掉的子串在该位后面，则贡献为：$d{\sum }_{j=1}^{n-j}j\times 10^{j-1}$

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<queue> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int N=100010; const ll mod=1e9+7; char s[N]; int n; int main() { IO; int T=1; //cin>>T; while(T--) { cin>>s+1; n=strlen(s+1); ll p=1,sum=0,res=0; for(int i=n;i;i--) { ll d=s[i]-'0'; res=(res+1ll*i*(i-1)/2%mod*d%mod*p%mod)%mod; res=(res+1ll*sum*d)%mod; sum=(sum+1ll*(n-i+1)*p)%mod; p=p*10%mod; } cout<<res<<'\n'; } return 0; }

D - Returning Home

Heltion大佬题解 第一次见这种建图方式，行列建图，如果$(i,j)$是一个特殊点那么在第$i$行的任意位置即可0代价到达$(i,j)$即到达了第$j$列，同理第$j$列的任意位置即可0代价到达$(i,j)$即到达了第$i$行。然后参考上述题解即可

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<queue> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> using namespace std; typedef long long ll; typedef pair<ll,int> pli; const int N=200010,M=2*N; const ll mod=1e9+7; const ll INF=1e17; int n,m; int sx,sy,fx,fy; vector<int> dx,dy; int x[N],y[N]; ll d[N]; int h[N],e[M],ne[M],idx; bool st[N]; void add(int a,int b) { e[idx]=b; ne[idx]=h[a]; h[a]=idx++; } int find(vector<int> &mp,int x)//无引用直接TLE { return lower_bound(mp.begin(),mp.end(),x)-mp.begin()+1; } void dijkstra() { priority_queue<pli,vector<pli>,greater<pli>> q; for(int i=1;i<=2*m;i++) if(d[i]!=INF) q.push({d[i],i}); while(q.size()) { int t=q.top().second;q.pop(); if(st[t]) continue; st[t]=1; for(int i=h[t];i!=-1;i=ne[i]) { int j=e[i]; if(d[j]>d[t]) q.push({d[j]=d[t],j}); } // 四个方向 // 行移动 if(1<=t&&t<=dx.size()) { if(t+1<=dx.size()&&d[t+1]>d[t]+dx[t]-dx[t-1]) { d[t+1]=d[t]+dx[t]-dx[t-1]; q.push({d[t+1],t+1}); } if(1<t&&d[t-1]>d[t]+dx[t-1]-dx[t-2]) { d[t-1]=d[t]+dx[t-1]-dx[t-2]; q.push({d[t-1],t-1}); } } // 列移动 if(m<t&&t<=dy.size()+m) { if(t+1<=dy.size()+m&&d[t+1]>d[t]+dy[t-m]-dy[t-1-m]) { d[t+1]=d[t]+dy[t-m]-dy[t-1-m]; q.push({d[t+1],t+1}); } if(m+1<t&&d[t-1]>d[t]+dy[t-1-m]-dy[t-2-m]) { d[t-1]=d[t]+dy[t-1-m]-dy[t-2-m]; q.push({d[t-1],t-1}); } } } } int main() { IO; int T=1; //cin>>T; while(T--) { cin>>n>>m; cin>>sx>>sy>>fx>>fy; memset(h,-1,sizeof h); for(int i=1;i<=m;i++) { d[i]=d[i+m]=INF;// 初始化 cin>>x[i]>>y[i]; dx.push_back(x[i]); dy.push_back(y[i]); } // 离散化坐标 sort(dx.begin(),dx.end()); sort(dy.begin(),dy.end()); dx.erase(unique(dx.begin(),dx.end()),dx.end()); dy.erase(unique(dy.begin(),dy.end()),dy.end()); for(int i=1;i<=m;i++) { int u=find(dx,x[i]); int v=find(dy,y[i]); add(u,m+v); add(m+v,u); d[u]=min(d[u],(ll)abs(sx-x[i])); d[m+v]=min(d[m+v],(ll)abs(sy-y[i])); } dijkstra(); ll res=abs(sx-fx)+abs(sy-fy); for(int i=1;i<=m;i++) { int u=find(dx,x[i]); res=min(res,abs(fx-x[i])+abs(fy-y[i])+d[u]); } cout<<res<<'\n'; } return 0; }

F - Boring Queries

静态版本题解都看不懂的渣渣，先标记一下，以后会了补！

最近数电信号要顶不住了啊啊啊啊啊 要加油哦！！！