2 条题解

  • 3
    #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;
    }
    
    • 2
      @ 2022-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
    上传者