D 选数

搜索; 2002; NOIP 普及组; 深度优先搜索 DFS; 剪枝; 素数判断,质数,筛法

#include<iostream>
#include<cstdio>
using namespace std;
int n,k;
int a[25];
bool isprime(int n)
{
	if(n<2)
	return false;
	if(n==2)
	return true;
	for(int i=2;i*i<=n;i++)
	{
		if(n%i==0)
		return false;
	}
	return true;
}
int dfs(int choose,int asum,int start ,int end)//递归函数   
{     int sum=0,i;
	if(choose==0)return  isprime(asum);  //当choose选完，判断asum是不是素数
		
	for(i=start;i<=end;i++) // 遍历开始到最后  全组合 
	{
		sum=sum+dfs(choose-1,asum+a[i],i+1,end); 
	}
	return sum;
}
int main()
{
	cin>>n>>k;
	for(int i=0;i<n;i++)
	cin>>a[i];
	cout<<dfs(k,0,0,n-1)<<endl;(chose，choose==0，从零开始，到结尾)
	return 0;
}

E 纪念品分组

贪心 排序

尽可能的少分点组，尽量都分成两个纪念品，从大的开始组队，如果最大的与最小的都配不上队说明绝对不能配成两个，只能是一个；

排序  利用双指针 去遍历结果  

将最大的与最小的和  跟最大限额比较，如果 和不大于限额  就组数加一 左指针和右指针 变化

反之 就移动右指针 组数加一

#include<bits/stdc++.h>
long long n,w,c=0;
int p[30005];
using namespace std;
int main()
{
	scanf("%lld",&w);
	scanf("%lld",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&p[i]);
	}
	sort(p,p+n);
	int l=0;
	int r=n-1;
	int cnt=0;
	while(l<=r)
	{
		if(p[l]+p[r]<=w)
		{
			cnt++;
			l++;
			r--;
			
		}
		else
		{
			cnt++;
			r--;
		}
	}
	cout<<cnt<<endl;

	return 0;


}

I '-'与‘_’配对 -_- 

数学组合

将上和下面的符号分别统计 

#include<iostream>
#include<cstdio>
using namespace std;
int t;
long long u,d;
long long   n;
char s[200005];
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		u=0;
		d=0;
		scanf("%lld",&n);
		scanf("%s",s);
		for(int i=0;i<n;i++)
		{	
		if(s[i]=='-')
  	            u++;
		if(s[i]=='_')
		    	d++;
		}
	 long long l=u/2;
	 long long  r=u-l;
	printf("%lld\n",l*r*d);// int*int*int 超范围  改为long long ; 

	}
	
	return 0;
}

J 斐波那契数列

ai+2 = ai + ai+1

题目中ai+2 = ai + ai+1 , 其中1<=i <=3,当 i = 1  a3 = a1 + a2  当 i = 2 时 a4 = a2 + a3 

当 i = 3 时 a5 = a3 + a4

  其中  符合的情况有 两种或者是三种都符合 

a3=a1+a2

a3=a4-a2

a3=a5-a4 

#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
	int a1,a2,a3,a4,a5;
	int num1,num2,num3;
	int t;
	cin>>t;
	while(t--)
	{
		int cnt=0;
		cin>>a1>>a2>>a4>>a5;
		num1=a1+a2;
		num2=a4-a2;
		num3=a5-a4;
		if(num1==num2||num1==num3||num2==num1&&num1==num3)
		{
			a3=num1;
		}
		else if(num2==num3)
			a3=num2;
		else
		a3=num3;
		if(a2+a1==a3)
		cnt++;
		if(a4-a2==a3)
		cnt++;
		if(a5-a4==a3)
		cnt++;
		cout<<cnt<<endl;
	}
	return 0;
}

B 两个字符合并为一个字符

strings

只要有相邻相同的 那么就会有最短长度 1 ；

其他情况都是 原长度

#include<iostream>
#include<cstdio>
using namespace std;
int t;
int l;
string s;
bool allsame=true;
int main()
{
	cin>>t;
	while(t--)
	{
		cin>>s;
		l=s.size();
		for(int i=0;i<l-1;i++)
		{
			if(s[i]==s[i+1])
			{
			allsame=true;
            break;//  当找不到时 跳出循环 不然会出错
			}
         else
			allsame=false;

		}
		if(allsame==false)
		cout<<l<<endl;
		else
		cout<<1<<endl;
		
	}
	
	return 0;
}

G  素数个数 

数学; 枚举; 素数判断,质数,筛法

素数筛

埃氏筛法

将合数筛去

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
bool pri[1000000005];
ll cnt;
int main()
{
	 ll n;
	 scanf("%lld",&n);
	 for(int i=2;i*i<=n;i++)
	 {
	 	if(!pri[i])
	 	for(int j=i*i;j<=n;j+=i)
	 	pri[j]=1;
	 }
	 for(int i=2;i<=n;i++)
	 {
	 	if(!pri[i])
	 	cnt++;
	 }
	 printf("%d\n",cnt);
	
		

	
	return 0;
}

欧拉筛  比埃氏筛快

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const int  maxn=1e8+10;
bool pri[maxn];
ll cnt;
ll pp=0;
int primes[maxn];
int main()
{
	 ll n;
	 scanf("%lld",&n);
	 for(ll i=2;i<=n;i++)
	 {
	 	if(!pri[i])
	 	primes[++pp]=i;
	 	for(int j=1;primes[j]*i<=n&&j<=pp;j++)
	 	{
	 		pri[primes[j]*i]=1;
	 		if(i%primes[j]==0)
	 		break;
		 }
	 }
	 for(ll i=2;i<=n;i++)
	 {
	 	if(!pri[i])
	 	cnt++;
	 }
	 printf("%lld\n",cnt);
	
		

	
	return 0;
}

F 乒乓球11分制和21分制

分制

• 条件 1：有一方的分数，达到或超过本局的 “目标分”（11 分制就是≥11，21 分制就是≥21）
• 条件 2：双方的分差，≥2 分（比如 11:9 可以结束，但 11:10 不行，要打到 12:10 才结束）

#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cstdlib>
using namespace std;
typedef long long ll;

string s;
int w=0,l=0;//WWWWWWWWWWWWWWWWWWWWWWLWE
void work (int lo)
{
	w=0;
	l=0;
	for(char c:s)
	{
		if(c=='E')
		break;
		if(c=='W')
		w++;
		if(c=='L')
		l++;
	
	if(max(w,l)>=lo&&abs(w-l)>=2)
	   {
		cout<<w<<":"<<l<<endl;
		w=0;
		l=0;
	   }
    }
   cout<<w<<":"<<l<<endl;

}
int main()
{
	string line;
	while(getline(cin,line)) //整段读入 刚开始用的cin>>s 为将后续字符串读入
	{
		s+=line;    //把刚读到的一行文字，拼接到总字符串 s 的后面
		if(line.find('E')!=string::npos)break;  //string::npos = 没找到
	}
	work(11);
	cout<<endl;
	work(21);
	return 0;
}