Problem - A - Codeforces
题目大意:给定长度为n的排列,每组排列有山峰数k,请你进行构造使得n的排列恰好有k个山峰.
模拟题:首先山峰的最大数量为(n-1)/2,如果超过这个数那必然无法构造出来,然后再根据k的数量,从大到小放置n, n-1, n-2,…就可以了.
#include<bits/stdc++.h>
using namespace std;
#define rep(x,y,z) for(int x = y; x<=z;++x)
#define dec(x,y,z) for(int x = y; x>=z;--x)
#define INF 0x3f3f3f3f
#define ll long long
#define LOOP ll _; cin>> _; for(ll LP_ = 1; LP_<=_; ++LP_)
#define syncfalse ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
inline int read(){
int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();return s*w;
}int main(){
LOOP{
int n, k;cin>>n>>k;int num = (n-1)/2;if (k > num)cout<<-1<<endl;else{
int right = n;int left = 1;while(k--){
cout << left++ << " ";cout << right-- << " ";}while(left <= right){
cout << left++ << " ";}cout <<endl;}}return 0;
}
Problem - B - Codeforces
题目大意:对于一个序列a1,a2,…an,其中对任意一个j而言,满足a1&a2&…&aj = aj+1&aj+2&…&an,我们称这样的序列是一个good序列,下面给你一个序列,请问该序列有多少种排列方式,使得整个序列是一个good序列.
思路:首先要明确的一点就是,为了使对于任意j,左半边和右半边的&运算结果都相等,那么一定有两个相同且所有位上匹配值最低的数放在两边,(这里的匹配值指的是所有位上,1尽可能地少,与其他数尽可能不重叠,这样的话才能保证无论和谁进行&运算,运算结果一定是它本身),那么这个匹配值最低的数一定是a1&a2&…&an,然后对于其他位上的数,可以进行全排列,理清楚了思路,代码实现就比较简单.
#include<bits/stdc++.h>
using namespace std;
#define rep(x,y,z) for(int x = y; x<=z;++x)
#define dec(x,y,z) for(int x = y; x>=z;--x)
#define INF 0x3f3f3f3f
#define ll long long
#define LOOP ll _; cin>> _; for(ll LP_ = 1; LP_<=_; ++LP_)
#define syncfalse ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
inline int read(){
int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();return s*w;
}
const int mod = 1e9+7;
map<ll, ll>a;
const int MAX = 2e5+5;
ll b[MAX];
int main(){
LOOP{
int n;cin>>n;a.clear();rep(i,1,n){
cin>>b[i];a[b[i]]++;}ll temp = b[1];rep(i,2,n){
temp &= b[i];}if (a[temp] < 2){
cout << 0 <<endl;}else{
ll ans= a[temp] * (a[temp]-(ll)1) % mod;for(ll i = 1; i <= n-2; ++i){
ans *= i;ans %= mod;}cout << ans <<endl;}}return 0;
}
Problem - C - Codeforces
题目大意:现在对于一个仅由数字,规定一种这样的加法,对于该数字的每一位,都加上1,如果当前数字为9,那么就变为10,例如1912 + 1 = 21023,现在给定一个这样的数字,求出它加上k次之后得到的数字的位数.
思路:一道递推题,因为k的输入规模是2e5,所以可以直接模拟出k的每一种情况,先用一个数组num存下当前0~9每个字符的个数,每次+1之后,字符的个数依次向前移动一位,1的字符个数额外的加上之前9的字符个数,然后根据这个关系递推即可,因为面临多组输入,所以需要预处理,并将每个k的值存入数组dp,dp的意义是当前数字经过+m之后得到的长度,最后对于每个输入的数字n,将n的每一位数字拿出来进行运算.(需要优化读写)
#include<bits/stdc++.h>
using namespace std;
#define rep(x,y,z) for(int x = y; x<=z;++x)
#define dec(x,y,z) for(int x = y; x>=z;--x)
#define INF 0x3f3f3f3f
#define ll long long
#define LOOP ll _; cin>> _; for(ll LP_ = 1; LP_<=_; ++LP_)
#define syncfalse ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
inline int read(){
int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();return s*w;
}
const int mod = 1e9+7;
ll num[10];
ll n, m;
const int MAX = 2e5+10;
ll ans =0;
ll dp[MAX];
int main(){
syncfalsememset(num, 0, sizeof(num));num[0] = 1;rep(i,1,MAX-1){
ll temp = num[9];dec(j,9,1){
num[j] = num[j-1];}num[0] =temp;num[0] %= mod;num[1]+=temp;num[1] %= mod;rep(j,0,9){
dp[i] += num[j];dp[i] %= mod;}}LOOP{
ans = 0;cin>>n>>m;while(n){
ll now = n %10;ans += dp[now+m];ans %= mod;n /= 10;}cout << ans << endl;}return 0;
}
Problem - D - Codeforces
题目大意:给定n个节点,和一个值p,每两个相邻节点存在一条边权为p的边,现在如果满足gcd(a1, a1+1,ai+2, …, aj) = min(a1, a1+1,ai+2, …, aj),那么i和j之间就存在一条边权为gcd(a1, a1+1,ai+2, …, aj)的边,现在对于整张图求其最小生成树.n<=2e5
思路:首先不能直接套用最小生成树的模板来做,因为n的值较大,这个图是根本建不起来的,但同时又需要有一种数据结构来表示连通关系,所以这里可以采用并查集来做.然后是如何考虑边权的问题,对于gcd(ai, ai+1,ai+2, …, aj) = min(ai, ai+1,ai+2, …, aj),如果满足该式子,那么ai就是最大质因数,其他所有能和它连边的节点值,都应该是它的倍数,然后对于这样的一个点,我们可以向左右两边分别进行连接,如果ai小于p,那么一定优先采用这种方式建图.为了降低复杂度,我们对原输入进行一个排序,先从较小的数值开始向两边举.当完成了gcd的建图之后,对于每相邻的两个节点,如果不连通,那么用边权为p的边再将其连上.
#include<bits/stdc++.h>
using namespace std;
#define rep(x,y,z) for(int x = y; x<=z;++x)
#define dec(x,y,z) for(int x = y; x>=z;--x)
#define INF 0x3f3f3f3f
#define ll long long
#define LOOP ll _; cin>> _; for(ll LP_ = 1; LP_<=_; ++LP_)
#define syncfalse ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
inline int read(){
int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();return s*w;
}
int par[200005];
int _rank[200005];
int n, m;
struct cpp{
int num, index;
}a[200005];
int b[200005];
bool cmp1(cpp&x, cpp&y){
return x.num < y.num;
}void init(int n){
rep(i,1,n)par[i] = i;
}int find(int a){
if (a == par[a])return a;else return par[a] = find(par[a]);
}void unite(int a, int b){
a = find(a), b = find(b);if (a == b)return;if (_rank[a] < _rank[b]){
par[a] = b;}else{
par[b] = a;_rank[a]++;}
}bool isSame(int a, int b){
return find(a) == find(b);
}int main(){
LOOP{
int p;n = read(), p = read();rep(i,1,n){
a[i].index = i;a[i].num = read();b[i] = a[i].num;}sort(a+1, a+1+n, cmp1);ll ans = 0;init(n);rep(i,1,n){
if (a[i].num < p){
int now = a[i].index;int nownum = a[i].num;int left = now-1, right = now+1;while(left > 0){
if (b[left] % nownum == 0 && !isSame(left, now)){
ans += nownum;unite(now, left);}else break;left--;}while(right <= n){
if (b[right] % nownum == 0 && !isSame(right, now)){
ans += nownum;unite(now, right);}else break;right++;}}else break;}rep(i,2,n){
if (!isSame(i-1, i)){
ans+=p;unite(i-1, i);}}cout << ans <<endl;}return 0;
}