2020牛客国庆集训派对day8

牛客网链接

文章目录

    • Easy Chess
    • 题意:
    • 题解:
    • Easy Problemset
    • 题意
    • 题解:
    • Shuffle Cards
    • 题解:
    • Diff-prime Pairs
    • 题意
    • 题解:
    • 代码:

Easy Chess

题意:

通过n步从左下角走到右上角,每次移动都是直线,每个格子只能停留一下,输出停留过的格子

题解:

队友做的

#include
using namespace std;
int n;
bool vis[10][10];
int main(){
     
	scanf("%d",&n);
	printf("a1 ");
	vis[1][1]=vis[8][8]=1;
	int x=1;
	int y=1;
	n--;
	while(n--){
     
		if(n<=2&&x!=8&&y!=8){
     
			y=8;
		}
		else{
     
			int f=0;
			for(int i=8;i>=1;i--){
     
				if(vis[i][y]==0){
     
					f=i;
					break;
				}
			}
			if(f==0){
     
				y++;
			}
			else{
     
				x=f;
			}
		}
		vis[x][y]=1;
		printf("%c%d ",(x-1)+'a',y);
	}
	printf("h8");
	return 0;
} 

Easy Problemset

题意

n个人轮流说数,如果说的数>=之前记录的数的和,就记录下来并加和,问m个满足条件的数的和是多少?如果不满m个就用50补充到m

题解:

签到题
按照题意模拟操作就可以

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define MAX 110
#define INF 0x3f3f3f3f
#define EXP 1e-9
#define DEUBG 0

using namespace std;

typedef long long ll;

int n,m,t,k;
int g[MAX][MAX];

int main(){
     
	int mx=-1;
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++){
     
		scanf("%d",&m);
		g[i][0]=m;
		mx=max(m,mx);
		for(int j=1;j<=m;j++){
     
			scanf("%d",&g[i][j]);
		}
	}
	int cnt=0;
	int sum=0;
	for(int i=1;i<=mx;i++){
     
		for(int j=0;j<n;j++){
      //row
			if(i<=g[j][0]&&g[j][i]>=sum){
     
				sum+=g[j][i];
				cnt++;
				if(cnt>=k){
     
					break;
				}
			}
			else if(i>g[j][0]){
     
				sum+=50;
				cnt++;
			}
		}
		if(cnt>=k)break;
	}
	sum+=(k-cnt)*50;
	printf("%d\n",sum);
	return 0;
}

Shuffle Cards

n个数(起始顺序为1~n),m个操作,操作x y意思为将第x位的数以及往后y个,一共y个数,移动到最前面,
问全部操作完后,最终结果是什么

题解:

STL的rope求解
Rope其主要是结合了链表和数组各自的优点,链表中的节点指向每个数据块,即数组,并且记录数据的个数,然后分块查找和插入。在g++头文件中,< ext / rope >中有成型的块状链表,在using namespace__gnu_cxx;空间中,其操作十分方便。

#include
#include
using namespace std;
__gnu_cxx::rope<int> f;
int main()
{
     
	int n, m;
	
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++)
		f.push_back(i);
	for(int i = 0; i < m; i++)
	{
     
		int l,r;
		cin>>l>>r;
		f = f.substr(l - 1, r)+f.substr(0,l-1)+f.substr(l + r - 1, n-l-r+1);
	}
	for(int i = 0; i < n; i++){
     
			cout<<f[i]<<" ";
	}
	return 0;
}

Diff-prime Pairs

题意

求序对(x,y),
x和y都小于等于N,且x/gcd(x,y)和y/gcd(x,y)都是质数
问有多少这样的序对?

题解:

多列几个例子就不难发现,当x和y为质数的倍数时就是满足条件的
比如n=6,就有
2 3
3 2
2 5
5 2
3 5
5 3
同时还有4 6,
4 6为2 3 的倍数,其实用n/3就可以得到
所以就是n/prme * i,其中prime为质数从3开始

代码:

#include 
#include 
#include 
using namespace std;
long long ans=0;
int n;
void get_prime(vector<int> & prime,int upper_bound){
      // 传引用
    if(upper_bound < 2)return;
    vector<bool> Is_prime(upper_bound+1,true);
    for(int i = 2; i <= upper_bound; i++){
     
        if(Is_prime[i]){
     
        	prime.push_back(i);
		}   
        for(int j = 0; j < prime.size() and i * prime[j] <= upper_bound; j++){
     
            Is_prime[ i*prime[j] ] = false;
            if(i % prime[j] == 0)break;// 保证了一个数只被筛一次。
        }
    }
}
int main(){
     
	scanf("%d",&n);
    vector<int> prime;
    get_prime(prime,n);
    for(int i=1;i<prime.size()&&prime[i]<=n;i++){
     
    	ans=ans+(long long)(n/prime[i])*i;
	}
	cout<<ans*2;
//    for(vector :: iterator it = prime.begin(); it not_eq prime.end(); it++)
//        cout<<*it<<" ";
    return 0;
}

你可能感兴趣的