A - Weather Forecast

AC代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<deque>
using namespace std;
void solve()
{int n;cin>>n;string s;cin>>s;if(s[n-1]=='o') puts("Yes");else puts("No");
}
signed main()
{solve();return 0;
}

B - qwerty

B - qwerty

AC代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<deque>
using namespace std;
const int N=30;
int p[N];
void solve()
{for(int i=1;i<=26;i++) cin>>p[i];for(int i=1;i<=26;i++) cout<<(char)('a'+p[i]-1);
}
signed main()
{solve();return 0;
}

C - Shapes

暴力模拟

逆时针旋转90度,最多旋转4次

平移是整体平移,不能超出边界

然后对于每一次旋转过后,找到s中的图形起点以及t中的图形起点,算出它们的偏移量,然后枚举s,如果是#的话,判断偏移后对应t的位置是否超出边界以及是不是#

AC代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<set>
using namespace std;
typedef pair<int,int>PII;
const int N=210;
int tmp[N][N];//中间数组,作为中转站
int s[N][N],t[N][N];
char ss[N][N];
int n;
//找起点
PII find(int a[N][N]){for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(a[i][j]==1) return {i,j}; }}
}
//逆时针旋转90度
void rotate()
{for(int i=0;i<n;i++){for(int j=0;j<n;j++){tmp[n-i-1][j]=s[j][i];}}for(int i=0;i<n;i++){for(int j=0;j<n;j++){s[i][j]=tmp[i][j];}}
}
int cnt1,cnt2;
void solve()
{cin>>n;for(int i=0;i<n;i++){for(int j=0;j<n;j++){cin>>ss[i][j];if(ss[i][j]=='#') {cnt1++;s[i][j]=1;}}}for(int i=0;i<n;i++){for(int j=0;j<n;j++){cin>>ss[i][j];if(ss[i][j]=='#') {cnt2++;t[i][j]=1;}}}//特判if(cnt1!=cnt2){puts("No");return;}//逆时针旋转4次for(int k=1;k<=4;k++){rotate();auto sxy=find(s);auto txy=find(t);int x1=sxy.first,y1=sxy.second;int x2=txy.first,y2=txy.second;int xdiff=x2-x1,ydiff=y2-y1;//s的起点与t的起点的偏移量bool flag=true;for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(s[i][j]==1){int nx=i+xdiff,ny=j+ydiff;if(nx<0||nx>=n||ny<0||ny>=n){flag=false;break;}if(t[nx][ny]==0){flag=false;break;}}}if(!flag) break;}if(flag){puts("Yes");return;}}puts("No");
}
signed main()
{solve();return 0;
}

D - Rectangles

我一开始做的思路是暴力求解,先将横坐标存入set1中，用vector将每个横坐标和它的纵坐标联系起来,枚举横坐标,对于其纵坐标,存入set2中,然后枚举后面的横坐标的纵坐标,数有多少个纵坐标和前面的纵坐标相同,记为cnt,则res+=cnt*(cnt-1)/2

用了三重循环O(n^3),超时了

RE代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<set>
#define int long long
using namespace std;
void solve()
{int n;cin>>n;vector<vector<int>>e(n+1);set<int>se;for(int i=1;i<=n;i++){int x,y;cin>>x>>y;se.insert(x);e[x].push_back(y); }int res=0;int cnt=0;for(auto it=se.begin();it!=se.end();it++){set<int>sse;
//        sse.clear();int i=*it;for(int j=0;j<e[i].size();j++){sse.insert(e[i][j]);}it++;for(auto iit=it;iit!=se.end();iit++){cnt=0;int m=*iit;for(int k=0;k<e[m].size();k++){if(sse.count(e[m][k])) cnt++;}res+=cnt*(cnt-1)/2;}it--;}cout<<res<<endl;
}
signed main()
{solve();return 0;
}

可以将所有坐标都放入set中,然后二重循环枚举每一对点,每一对点枚举两遍,当该对点是从左下往右上时,判断从右下往左上的点是否存在，如果存在，则组成一个矩形

AC代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<set>
using namespace std;
void solve()
{int n;cin>>n;set<pair<int,int>>se;for(int i=0;i<n;i++){int x,y;cin>>x>>y;se.insert({x,y});}int res=0;for(auto v:se){int a=v.first,b=v.second;for(auto u:se){int c=u.first,d=u.second;if(a<c&&b<d)if(se.count({a,d})&&se.count({c,b})) res++;}}cout<<res<<endl;
}
signed main()
{solve();return 0;
}

E - Destruction

假设边权都是正的

用kruscal算法求出最小生成树,保证在联通的情况下,边权之和最小

这样的话,其它边都可以删除,则获得的奖励最多

边权是负的话不需要管,因为题目只要求联通,成环是没关系的,所以只要将所有负的边全部都加到刚才的最小生成树中就可以了

AC代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<set>
#include<map>
#define int long long
using namespace std;
const int N=2e5+10;
int n,m;
int p[N];
struct edge{int a,b,w;bool operator<(const edge &W)const{return w<W.w;}
}edges[N];
int find(int x){if(x!=p[x]) p[x]=find(p[x]);return p[x];
}
void solve()
{cin>>n>>m;for(int i=0;i<m;i++){int a,b,w;cin>>a>>b>>w;edges[i]={a,b,w};}sort(edges,edges+m);for(int i=1;i<=n;i++) p[i]=i;map<int,int>mp;for(int i=0;i<m;i++){int a=edges[i].a,b=edges[i].b,w=edges[i].w;a=find(a),b=find(b);if(a!=b){p[a]=b;mp[i]++;}}int res=0;for(int i=0;i<m;i++){if(!mp[i]){if(edges[i].w>0) res+=edges[i].w;}}cout<<res<<endl;
}
signed main()
{solve();return 0;
}

F - Blocked Roads

参考Cutele_

先全部边跑一遍最短路,最短路记为res,并记录下最短路的边

枚举m条边,看是不是最开始记录下边,如果不是的话,直接输出的最短路的res

否则重新跑一遍最短路(不用第i条边)

AC代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<set>
using namespace std;
const int N=2e5+10;
int n,m;
typedef pair<int,int>PII;
vector<int>g[N];
PII edges[N];//记录边
int dist[N];//从起点到某点的最短距离
bool st[N];//标记某点是否走过
int pre[N];//记录最短路径的某点的上一个点是哪一个点
set<PII>se;
//spfa算法求最短路
int bfs(int x){memset(dist,0x3f,sizeof dist);memset(st,0,sizeof st);queue<int>q;q.push(1);dist[1]=0;st[1]=true;while(q.size()){int t=q.front();if(t==n) return dist[n];q.pop();st[t]=false;for(auto v:g[t]){//如果第x条边的前端点是t,后端点是v,那么跳过这条边,相当于删除if(edges[x].first==t&&edges[x].second==v) continue;if(dist[v]>dist[t]+1){dist[v]=dist[t]+1;if(x==0) pre[v]=t;//第一遍跑最短路时把最短路的路径都记下来if(!st[v]){q.push(v);st[v]=true;}}}}return -1;
}
void solve()
{cin>>n>>m;for(int i=1;i<=m;i++){cin>>edges[i].first>>edges[i].second;g[edges[i].first].push_back(edges[i].second);}int res=bfs(0);//res即为第一遍跑最短路的最短路径//把第一遍跑的最短路的最短路径放入set中,方便后续查询边是不是最短路径中的边//从终点n往前推int now=n;while(now!=1){if(!pre[now]) break;PII tmp={pre[now],now};now=pre[now];se.insert(tmp);}//如果是最短路径,则跳过这条边重新跑一遍最短路//否则输出resfor(int i=1;i<=m;i++){if(se.count(edges[i])) printf("%d\n",bfs(i));else cout<<res<<endl;}
}
signed main()
{solve();return 0;
}