比赛链接:https://vjudge.csgrandeur.cn/contest/518332#overview
A题:大意是给出一个字符串,字符串遇到aeiou就会翻转,并将元音放到最开头,求出有多少种可能可以构造这个字符串。
两种最容易发现的情况,不存在元音为1,存在一个元音不为开头为0。
其他的情况我们只考虑最后的,当元音为1且开头时,存在strlen(s)种情况。
其他情况是中间的两个辅音的数量+1。
这里的推论应该通过队友的打表来找规律,但是没有配合起来。
code:
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize(2) #define ll long long inline int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} return x*f; } bool panduan(char c){ if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u') return true; return false; } int main() { //cin.ignore(numeric_limits<streamsize>::max(),'\n') //ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); string s; cin>>s; vector<int>ve; for(int i=0;i<s.size();i++){ if(panduan(s[i])) ve.push_back(i); } int n=ve.size(); if(n==0) cout<<1<<endl; else if(ve[0]!=0) cout<<0<<endl; else if(n==1){ cout<<s.size()<<endl; }else{ int x = ve[(n+1)/2-1],y = ve[(n+1)/2]; cout<<y-x<<endl; } }
G题:大意是给出n个小偷的坐标和m个照明灯的坐标,然后判断所有小偷同时走多少步可以使得所有小偷逃离照明灯的位置。
照明灯可以照亮小于等于行列的范围。
贪心思想考虑这个问题,如果小偷的x在照明范围,我们用y去更新它。这样我们大致记录了一个较优的值。
取出每一个较优的y值,然后反向一遍获取最后的最优解。为什么要反向,因为我们希望获得的x差值是个较大的,这样的解才是最大的优解。
code:
#include<bits/stdc++.h> #define ll long long #define INF 0x7f7f7f7f //2139062143 #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; const ll maxn=2e3+7; int n,m; int a[maxn],b[maxn],c[maxn],d[maxn]; int cas[1000007];//cas[i]记录的是在对x选择增加的值最大为i的情况下,需要对y增加的最小值。注意此处仅对单个灯的情况进行了考虑,并不是完全的 int32_t main() { IOS; cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]>>b[i]; for(int i=1;i<=m;i++) cin>>c[i]>>d[i]; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(c[j]>=a[i]) cas[c[j]-a[i]]=max(cas[c[j]-a[i]],d[j]-b[i]+1);//对于每个灯,如果x的移动没有使得第i个人离开了第j盏灯的范围,那就需要在y上进行移动 } } int ans=INF,y=0; for(int i=1000001;i>=0;i--)//cas[i]记录的值并不完备,对与i=x的情况,i>x的所有情况对应的y上限也应该被满足,因此反向for一遍取一下最小值即可 { y=max(y,cas[i]); ans=min(ans,i+y); } cout<<ans<<endl; }
E题:大腿题。我们当时AC的时候,只有一个山大的队做出了这个题,队友做的时候我是极力反对的。。。。</打脸>
大意是给出一个存在黑白的矩形,然后判断里面的黑块是个几边形。
多边形的边数和顶点数相等,所以等效于算顶点数,形成一个正方
形的四个相连块中,如果有一个或者三个是黑色,说明是一个”拐
点“,也就是多边形的顶点。
队友ac了,这个性质确实不知道。估计要推算一段时间。
code:
#include<bits/stdc++.h> using namespace std; #define int long long #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); const int N=35; char mapp[N][N]; int cnt; int ans; int r,c; void solved(int x,int y) { if(mapp[x][y]=='#') cnt++; if(mapp[x+1][y]=='#') { cnt++; } if(mapp[x+1][y+1]=='#') cnt++; if(mapp[x][y+1]=='#') cnt++; if(cnt==1||cnt==3) ans++; } signed main() { IOS; cin>>r>>c; for(int i=0;i<r;i++) { for(int j=0;j<c;j++) { cin>>mapp[i][j]; } } for(int i=0;i<r;i++) { for(int j=0;j<c;j++) { cnt=0; solved(i,j); } } cout<<ans<<endl; return 0; }