第十一届“图灵杯“NEUQ-ACM程序设计竞赛

补题！！！

A-古堡中的勇者

题意

给出勇者和守卫的位置，并且勇者的位置在守卫之间，勇者可以向相邻位置移动，求解勇者最多能收集的宝物。

思路

只要宝物所处的位置在守卫的位置之间就可以获得。

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,c;
	cin>>a>>b>>c;
	int n;
	cin>>n;
	int x;
	int ans=0;
	for(int i=1;i<=n;i++){
		cin>>x;
		if(b<x&&x<c)
		ans++;
	}
	cout<<ans<<endl;
	return 0;	
} 

C-我就要不协调 

题意

给定一个序列，使用最少的操作次数使得该序列变为单调下降子序列。

思路

只要有一个单调下降子序列即可符合要求，我们就要寻找相邻的单调上升序列，若想把两个数从上升变为下降需要操作(b-a)/2+1次；依次求取其最小值。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+9;
int a[N];
void solve()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	int ans=INT_MAX,temp;
	for(int i=2;i<=n;i++){
		if(a[i]>=a[i-1]){
			temp=(a[i]-a[i-1])/2;
			ans=min(ans,temp+1);
		}
		else{
			ans=0;
			break;
		}
	}
	cout<<ans<<endl;
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;	
} 

E-字母匹配

题意

每个英文字母的大小写相匹配，每次操作可将字母的大小写进行反转，在进行k次操作之后，求解匹配成功的字母对数。

思路

首先将每个字母所匹配的大写或小写字母进行标记，字符串在进行操作之前的字母对数为每个字母当中大写和小写字母的最小值，剩余未匹配的需要进行abs(大写字母个数-小写字母个数)/2次操作才可匹配成功。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+9;
int a[N],b[N],vis[N],p[N];
void solve()
{
	for(int i=65;i<=90;i++){
		b[i]=i+32;
		b[i+32]=i;
	}
	int n,k;
	cin>>n>>k;
	string s;
	cin>>s;
	for(int i=0;i<n;i++){
		a[s[i]]++;
	}
	int res=0,temp=0,x=0;
	for(int i=0;i<n;i++){
		if(!vis[s[i]]){
			vis[s[i]]=1;
			vis[b[s[i]]]=1;
			temp+=min(a[s[i]],a[b[s[i]]]);
		}
	}
//	cout<<temp<<endl;
	int f=0;
//	cout<<a[97]<<" "<<a[65]<<endl;
	for(int i=0;i<n;i++){
		if(!p[s[i]]){
			p[s[i]]=1;
			p[b[s[i]]]=1;
			x+=abs(a[s[i]]-a[b[s[i]]])/2;
		}
		if(x>k){
			f=1;
			break;
		}
	}
//	cout<<x<<endl; 
	if(!f) cout<<temp+x<<endl;
	else cout<<temp+k<<endl;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t=1;
//	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;	
} 

H-卷王

题意

给出这次考试学生的成绩以及小D的排名和下次考试的成绩，求解小D在经过下次考试后能获得的最佳排名是多少。

思路

小D想获得最佳排名，所以小D应该加上下次考试中成绩最高的，在小D排名之前的人都要加上成绩最低的。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+9;
int a[N],b[N],vis[N],p[N];
void solve()
{
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		cin>>b[i];
	}
	a[k]+=b[1];
	int f=k;
	for(int i=1;i<k;i++){
		if(a[k]>=a[i]+b[n]){
			f=i;
			break;
		}
	} 
	cout<<f<<endl;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t=1;
//	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;	
} 

F-数学家的四不要

题意

求解在n之内除了偶数，质数，三角数，卡特兰数之外还有多少个数。

思路

分别对四种情况进行判断。

代码

#include<bits/stdc++.h>
#define int long long
const int N=2e5+9;
using namespace std;
int a[N],b[N],vis[N],prime[N];
void solve()
{
	int n,count=0,k=0;
	cin>>n;
	for(int i=2;i<=n;i++)
    { 
      if(!a[i])
      {
       		prime[++k]=i;
      }	
      for(int j=1;j<=k&&i*prime[j]<=n;j++)
      {
	   	   a[i*prime[j]]=1;
	   	   if(i%prime[j]==0) break;
      }
 	}
 	
	int x=0;
	for(int i=1;i<=n;i++){
		x+=i;
		vis[x]=1;
		if(x>n) break;
	}
	
	b[0]=b[1]=1;
	for(int i=2;i<=n;i++){
		x=0;
		for(int j=0;j<i;j++){
			x+=b[j]*b[i-1-j];
		}
		if(x>n) break;
		b[i]=x;
		vis[x]=1;
		
	}
	
	for(int i=9;i<=n;i++){
		if(i%2!=0&&a[i]&&!vis[i])
		count++;
	}
	cout<<count<<endl;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T;
	T=1;
	while(T--)
	{
		solve();
	}
	return 0;
}

I-字串比较 

题意

比较两个字符串对应区间的子字符串大小。

思路

利用字符串哈希，若两个子字符串不相等的话，利用二分查找找出子字符串最长相等的长度，然后比较其后第一个不相等位置的字符。

代码

#include<iostream>
using namespace std;
typedef unsigned long long ull;
const int N=2e5+10,p=131;
ull h1[N],p1[N],h2[N],p2[N];
int n,m,q;
ull get(ull h[],ull p[],int l,int r)
{
    return h[r]-h[l-1]*p[r-l+1];
}
int main()
{
    string s1,s2;
    cin>>n>>m>>q>>s1>>s2;
    p1[0]=p2[0]=1;
    for(int i=1;i<=n;i++) 
    {
        h1[i]=h1[i-1]*p+s1[i-1];
        p1[i]=p1[i-1]*p;
    }
    for(int i=1;i<=m;i++) 
    {
        h2[i]=h2[i-1]*p+s2[i-1];
        p2[i]=p2[i-1]*p;
    }
    while(q--)
    {
        int l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;
        if(get(h1,p1,l1,r1)==get(h2,p2,l2,r2)) cout<<"="<<endl;
        else
        {
            int l = 0, r = r1 - l1 + 1;
            int ans = 0;
            while (l <= r)
            {
                int mid = (l + r) / 2;
                if (get(h1, p1, l1, l1 + mid - 1) != get(h2, p2, l2, l2 + mid - 1)) r = mid - 1;
                else{
                	l = mid + 1;
					ans = mid;
				}
            }
            if (s1[l1 + ans - 1] < s2[l2 + ans - 1]) cout << "<" << endl;
            else cout << ">" << endl;
        }
    }
    return 0;
}