Codeforces 1284（A，B）hello 2020

本文主要是介绍Codeforces 1284（A，B）hello 2020，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

A. New Year and Naming

题意：有两个集合，分别是含有n个元素的s集合与含有m个元素的t集合，第x年的名字有s集合的第x%n（x%n=0是即为第n个元素）个元素与t集合的第x%m（x%m=0时同上）个元素的拼接。

思路：开两个二维数组分别存s集合与t集合，分别找到第x%n和第x%某个元素一起输出就好。

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=2*1e5+5;
char a[20][12],b[20][12];
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n,m,q;long long t;cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=m;i++)cin>>b[i];cin>>q;while(q--){cin>>t;int z=t%n,c=t%m;if(z==0) z=n;if(c==0) c=m;cout<<a[z]<<b[c]<<endl;}return 0;
}

B. New Year and Ascent Sequence

题意： 给你n个序列，每个序列含有ki个元素。其中两两拼接组成n²个新的序列（可以自己与自己拼接，同一个序列可被取用两次，主要看取出的顺序，即A+B和B+A），如果某个新序列中含有升序段（即i<j且ai<aj），那么这个新序列就是合法的，问能组成多少个合法序列。

思路： 之前想过用普通的数组遍历统计，后面才发现数据太大跑不过。没办法，我就只有去学习新知识了，哎，还是太弱了~
这个题用树状数组就很好做了。如果原本就是合法的序列，那么它和谁拼接都是合法的，遍历到它就ans+=n,如果原本的序列不合法，那么就要找到所有最小值比它的最大值小的序列个数x，再ans+=x；而要找到这个x就得用到树状数组来统计了O(n* log n)。

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long INF=0x3f3f3f3f;
const int MAXN=1e6+5;
long long a[MAXN][3];
long long sum[MAXN];
int lowbit(long long x)
{return x&(-x);
}
int add(long long x,long long y)
{while(x<MAXN){sum[x]+=y;x+=lowbit(x);}
}
int ask(long long x)
{long long res=0;while(x){res+=sum[x];x-=lowbit(x);}return res;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);long long n,res=0,ans=0;cin>>n;for(int i=1;i<=n;i++) a[i][1]=MAXN;for(int i=1;i<=n;i++){long long t;cin>>t;for(int j=1;j<=t;j++){long long tmp;cin>>tmp;a[i][1]=min(a[i][1],tmp);a[i][2]=max(a[i][2],tmp);if(tmp>a[i][1]) a[i][0]=1;}if(a[i][0]) res++;else add(a[i][1]+1,1);}for(int i=1;i<=n;i++){if(a[i][0]) ans+=n;else ans+=res+ask(a[i][2]);}cout<<ans<<endl;return 0;
}

这篇关于Codeforces 1284（A，B）hello 2020的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---