2 条题解
-
3http://www.temege.com/home/settings/domain (Laijunlin) LV 6 @ 2023-7-14 11:22:14
#include<stdio.h> #include <iostream> #include<cstring> #include<algorithm> using namespace std; const int N=1e5+10; const int INF=0x3f3f3f3f; int n; string s; int main() { cin>>n; getline(cin,s); for(int i=1;i<=n;i++) { getline(cin,s); int len=s.size(); for(int j=0;j<len;j++) { if(s[j]>='A'&&s[j]<='Z') { s[j]+=32; if(s[j]+i>'z') s[j]=s[j]+i-26; else s[j]+=i; } else if(s[j]>='a'&&s[j]<='z') { s[j]-=32; if(s[j]+i>'Z') s[j]=s[j]+i-26; else s[j]+=i; } } cout<<s<<endl; } return 0; }
-
22022-5-11 19:02:25@
方法一:差分约束
#include<bits/stdc++.h> #define k e[i].to using namespace std; int n,a[20001]={0},dis[20001]={0},home[20001]={0},cnt=0,ans=0; struct node{ int next,to; }e[40001]; void putin(int a,int b){ e[++cnt].to=b; e[cnt].next=home[a]; home[a]=cnt; } void Dijkstra(){ priority_queue<pair<int,int>,vector<pair<int,int> >,less<pair<int,int> > > q; q.push(make_pair(0,0)); while(!q.empty()){ int cnt=q.top().second; q.pop(); for(int i=home[cnt];i;i=e[i].next){ if(dis[k]<dis[cnt]+1){ dis[k]=dis[cnt]+1; q.push(make_pair(dis[k],k)); } } } } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); if(i>1){ if(a[i]>a[i-1]) putin(i-1,i); if(a[i-1]>a[i]) putin(i,i-1); } } for(int i=1;i<=n;i++) putin(0,i); Dijkstra(); for(int i=1;i<=n;i++){ ans+=dis[i]; } printf("%d",ans); return 0; }
方法二:拓扑排序
#include<bits/stdc++.h> using namespace std; int n,a[20001]={0},r[20001]={0},b[20001]={0},zhe[20001]={0},ans=0,now=1,cc=1; queue<int> q; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<n;i++){ if(a[i]>a[i+1]) r[i]++; else if(a[i]<a[i+1]) r[i+1]++; } for(int i=1;i<=n;i++) if(r[i]==0) q.push(i); while(!q.empty()){ int cnt=q.front(); q.pop(); b[cc]=cnt; cc++; if(a[cnt]<a[cnt+1]&&cnt<n){ r[cnt+1]--; if(r[cnt+1]==0) q.push(cnt+1); } if(a[cnt]<a[cnt-1]&&cnt>1){ r[cnt-1]--; if(r[cnt-1]==0) q.push(cnt-1); } } for(int i=1;i<=n;i++){ if(a[b[i]]>a[b[i]+1]&&zhe[b[i]+1]!=0){ now=max(now,zhe[b[i]+1]+1); } if(a[b[i]]>a[b[i]-1]&&zhe[b[i]-1]!=0){ now=max(now,zhe[b[i]-1]+1); } zhe[b[i]]=now; } for(int i=1;i<=n;i++) ans+=zhe[i]; printf("%d",ans); return 0; }
- 1
信息
- ID
- 1929
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- 递交数
- 617
- 已通过
- 105
- 上传者