Codeforces Round 900 (Div

Codeforces Round 900 (Div. 3)

A. How Much Does Daytona Cost?

这个题简单，在子段上最常见的元素其实只要这个元素出现就行

    int t;
	cin>>t;
	int n,k;
	while(t--)
	{
		cin>>n>>k;
		int arr[n];
		int out=0;
		for(int i=0;i<n;i++)
		{
			cin>>arr[i];
		}
		for(int i=0;i<n;i++)
		{
			if(arr[i]==k)
			{
				out=1;
				break;
			}
		}
		if(out==1)cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}

B. Aleksa and Stack

我最开始把a0=1，a1=2然后依次递推进行输出，递推中让i=1进行除法因为a[i+2]是整数，所以将(a[i]+a[i+1])++,使其能够得到一个整数a[i+2]并且a[i+2]和a[i]+a[i+1]的和由于递增的原因不会整除；后来交答案才发现可以直接构造一个2×i-1的奇数序列a[i]+a[i+1]为偶，3×a[i+2]为奇数，故不能整除；

long long t;
	scanf("%lld",&t);
	long long n;		
	while(t--)
	{
		scanf("%lld",&n);
		for(long long i=1;i<n;i++)
		{
			printf("%lld ",2*i-1);
		}
		printf("%lld\n",2*n-1);
	}

C. Vasilije in Cacak

这个题主要是分析x是否在原序列所形成的最小总和和最大总和之间，其中minsum，maxsum直接用等差数列求和公式就行

long long t;
	cin>>t;
	long long n,k,x;
	long long maxsum,minsum;
	while(t--)
	{
		cin>>n>>k>>x;
		maxsum=(2*n-k+1)*k/2;
		minsum=(1+k)*k/2;
		if(maxsum<x||minsum>x)cout<<"NO"<<endl;
		else cout<<"YES"<<endl;
	}

D. Reverse Madness

这个题思路很简单，就是在字符串两端点内会进行翻转，我们只需利用前缀和就能记录其翻转的次数，然后翻转次数为偶数就不用管，奇数就进行翻转，但是就是这个数据它下标的原因就不好处理，后面想到了将s=“ ”+s来更换下标。（由于查找效率过慢，手写了二分查找，后面才晓得可以直接upper_bound)

	int t;
	scanf("%d", &t);
	while (t--)
	{
	    int n, k; 
	    cin >> n >> k;
	    string s;
	    cin >> s;
	    s = " " + s;
	    vector<int> l(k + 1), r(k + 1);
	    for (int i = 1; i <= k; i++)
	        scanf("%d",&l[i]);
	    for (int i = 1; i <= k; i++)
	        scanf("%d",&r[i]);
	    int q;
	    scanf("%d",&q);
	    vector<int> cnt(n + 1, 0);
	    for (int i = 1; i <= q; i++)
	    {
	        int x;
	        scanf("%d",&x);
	        int pos = upper_bound(l.begin() + 1, l.end(), x) - l.begin() - 1; // 找到第一个大于他的数再前面一个就是他所在的区间
	        int temp = min(x, l[pos] + r[pos] - x);
	        cnt[temp]++; // 记录每个位置被翻转的次数
	    }
	    for (int i = 1; i <= k; i++)
	    {
	        int mid = (l[i] + r[i])/2;
	        int sum = 0;
	        for (int j = l[i]; j <= mid; j++)
	        {
	            sum += cnt[j];
	            if (sum %2 == 1)
	                swap(s[j], s[l[i] + r[i] - j]);
	        }
	    }
	    // cout << s << endl;有空格
	    for (int i = 1; i <= n; i++)
	       printf("%c",s[i]);
	    cout << endl;
	}

E. Iva & Pav

涉及位运算还没学后面补T____T