A. TubeTube Feed

分析:

從所有a[i]+i-1<=t的選擇種取個max即可

code:

#include <bits/stdc++.h>
using namespace std;
 
const int N = 55;
int a[N], b[N];
 
 
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	
	while (t --)
	{
		int n, m;
		cin >> n >> m;
		
		for (int i = 0; i < n; i ++)
			cin >> a[i];
			
		for (int i = 0; i < n; i ++)
			cin >> b[i];
			
		int s = 0, res = 0, idx = -1;
		bool flag = false;
		
		for (int i = 0; i < n; i ++)
		{
			if (s + a[i] <= m)
			{
				flag = true;
				if (b[i] > res)
				{
					res = b[i];
					idx = i + 1;
				}
			}
			s ++;	
		}
		
		if (!flag)
			cout << -1 << endl;
		else
			cout << idx << endl;
	}    
	
    return 0;
}

B. Karina and Array

分析:

實際上就是取同符號乘積的最大值

code:

#include <bits/stdc++.h>
using namespace std;
 
const int N = 2e5 + 5;
int a[N], b[N];
 
typedef long long LL;
 
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	
	while (t --)
	{
		int n;
		cin >> n;
		
		if (n == 2)
		{
			int num1, num2;
			cin >> num1 >> num2;
			
			cout << (LL)num1 * num2 << endl;
		}
		else
		{
			int cnt1 = 0, cnt2 = 0;
			
			for (int i = 0; i < n; i ++)
			{
				int x;
				cin >> x;
			
				if (x >= 0)
					a[cnt1 ++] = x;
				else
					b[cnt2 ++] = x;
			}
		
			sort(a, a + cnt1);
			sort(b, b + cnt2);
			
			LL res;
			if (cnt1 >= 2 && cnt2 >= 2)
			{
				res = max((LL)b[0] * b[1], (LL)a[cnt1 - 2] * a[cnt1 - 1]);
			}
			else if (cnt1 >= 2 && cnt2 < 2)
				res = (LL)a[cnt1 - 2] * a[cnt1 - 1];
			else if (cnt1 < 2 && cnt2 >= 2)
				res = (LL)b[0] * b[1];
			
			cout << res << endl;
		}
	}
	
    return 0;
}

C. Bun Lover

分析:

找規律，發現結果與邊長n的關系是：res = n * (n + 3) - (n - 2)

code:

#include <bits/stdc++.h>
using namespace std;
 
const int N = 2e5 + 5;
int a[N], b[N];
 
typedef long long LL;
 
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	
	while (t --)
	{
		LL n;
		cin >> n;
		
		cout << n * (n + 3) - (n - 2) << endl;
	}
	
    return 0;
}

D. Super-Permutation

分析:

①當n為奇數時，除了1其他均無解
②當n為偶數時，我們可以構造一個形如n,1,n - 2,3,...的數列
首先我們可以發現n必定出現在起始位置，如果n不在起始位置，假設在位置i，那么s[i - 1] % n == (s[i - 1] + n) % n = s[i] % n，
接著，考慮構造方式，最方便的即是考慮讓序列取模結果為：0，1，-1，2，-2...(-1取模意義下溢位實際上就是n - 1),按上述結果形式構造的序列n,1,n - 2,3,...即可滿足所有條件
最后從結果來看就是n在偶數位遞減，1在奇數位遞增，

code:

#include <bits/stdc++.h>
using namespace std;
 
const int N = 2e5 + 5;
int a[N];
 
int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	
	while (t --)
	{
		int n;
		cin >> n;
		
		if (n == 1)
			cout << 1 << endl;
		else if (n & 1)
			cout << -1 << endl;
		else
		{
			for (int i = 0, j = n; i < n; i += 2, j -= 2)
				a[i] = j;
			for (int i = 1, j = 1; i < n; i += 2, j += 2)
				a[i] = j;
			for (int i = 0; i < n; i ++)
				cout << a[i] << " ";
			cout << endl;
		}
	}
	
	return 0;
}

E. Making Anti-Palindromes

分析:

①當n為奇數時：根據定義無解，
②當n為偶數時：
當某個字符出現的次數大于n / 2時，根據容斥原理，一定存在s[i] = s[n - i + 1]，
若不存在上述情況則一定有解，考慮如何處理對稱字符：倘若存在形如..a..b..b..a的字符對我們優先選擇交換a和b，這樣一次操作可以處理兩對字符，否則將對稱對形如..a..b..d..a的情況交換a和d，一次操作處理一對字符，統計出現次數最多的字符對，其出現次數記為cnt1，所有字符對總數量記為cnt2，優先處理cnt1，所以當cnt1 <= cnt2 - cnt1時，答案即cnt2 / 2，否則答案即cnt1

code:

#include <bits/stdc++.h>
using namespace std;
 
const int N = 27;
int h[N], h2[N];
 
int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	
	while (t --)
	{
		int n;
		cin >> n;
		string s;
		cin >> s;
		
		if (n & 1)
			cout << -1 << endl;
		else
		{
			bool check = true;
			memset(h2, 0, sizeof h2);
			memset(h, 0, sizeof h);
			
			for (int i = 0; i < n; i ++)
			{
				h2[s[i] - 'a'] ++;
				if (h2[s[i] - 'a'] > n / 2)
				{
					check = false;
					break;
				}
			}
			
			
			if (check)
			{
				int Max = 0, cnt = 0;
				for (int i = 0, j = n - 1; i < n / 2; i ++, j --)
				{
					if (s[i] == s[j])
					{
						h[s[i] - 'a'] ++;
						Max = max(Max, h[s[i] - 'a']);
						cnt ++;
					}
				}
				
				if (Max <= cnt - Max)
					cout << (cnt + 1) / 2 << endl;
				else
					cout << Max << endl;
			}
			else
				cout << -1 << endl;
		}
	}
	
	return 0;
}

標籤：其他

上一篇：牛客小白月賽71

下一篇：返回列表