A. Even But Not Even
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
Let’s define a number ebne (even but not even) if and only if its sum of digits is divisible by 2 but the number itself is not divisible by 2. For example, 13, 1227, 185217 are ebne numbers, while 12, 2, 177013, 265918 are not. If you’re still unsure what ebne numbers are, you can look at the sample notes for more clarification.
You are given a non-negative integer s, consisting of n digits. You can delete some digits (they are not necessary consecutive/successive) to make the given number ebne. You cannot change the order of the digits, that is, after deleting the digits the remaining digits collapse. The resulting number shouldn’t contain leading zeros. You can delete any number of digits between 0 (do not delete any digits at all) and n−1.
For example, if you are given s=222373204424185217171912 then one of possible ways to make it ebne is: 222373204424185217171912 → 2237344218521717191. The sum of digits of 2237344218521717191 is equal to 70 and is divisible by 2, but number itself is not divisible by 2: it means that the resulting number is ebne.
Find any resulting number that is ebne. If it’s impossible to create an ebne number from the given number report about it.
Input
The input consists of multiple test cases. The first line contains a single integer t (1≤t≤1000) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer n (1≤n≤3000) — the number of digits in the original number.
The second line of each test case contains a non-negative integer number s, consisting of n digits.
It is guaranteed that s does not contain leading zeros and the sum of n over all test cases does not exceed 3000.
Output
For each test case given in the input print the answer in the following format:
If it is impossible to create an ebne number, print “-1” (without quotes);
Otherwise, print the resulting number after deleting some, possibly zero, but not all digits. This number should be ebne. If there are multiple answers, you can print any of them. Note that answers with leading zeros or empty strings are not accepted. It’s not necessary to minimize or maximize the number of deleted digits.
题意：
给一个数字字符串 求所有字符和能被2整除 且不是个偶数
思路：枚举最后一个数字 边求和 边判断最低位是不是奇数即可
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define me(a,x) memset(a,x,sizeof a)
#define pb(a) push_back(a)
#define pa pair<int,int>
#define fi first
#define se second
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
string s;
cin>>n>>s;
int sum=0;
for(int i=0; i<n; i++)
sum+=s[i]-'0';
if(((s[n-1]-'0')&1) &&(sum%2==0))
cout<<s<<endl;
else
{
sum=0;
string a;
int f=0;
for(int i=0; i<n; i++)
{
a+=s[i];
sum+=s[i]-'0';
if(sum%2==0 && ((s[i]-'0')&1))
{
f=1;
a[i+1]='\0';
cout<<a<<endl;
break;
}
}
if(!f) puts("-1");
}
}
return 0;
}
B. Array Sharpening
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
You’re given an array a1,…,an of n non-negative integers.
Let’s call it sharpened if and only if there exists an integer 1≤k≤n such that a1<a2<…ak+1>…>an. In particular, any strictly increasing or strictly decreasing array is sharpened. For example:
The arrays [4], [0,1], [12,10,8] and [3,11,15,9,7,4] are sharpened;
The arrays [2,8,2,8,6,5], [0,1,1,0] and [2,5,6,9,8,8] are not sharpened.
You can do the following operation as many times as you want: choose any strictly positive element of the array, and decrease it by one. Formally, you can choose any i (1≤i≤n) such that ai>0 and assign ai:=ai−1.
Tell if it’s possible to make the given array sharpened using some number (possibly zero) of these operations.
Input
The input consists of multiple test cases. The first line contains a single integer t (1≤t≤15 000) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer n (1≤n≤3⋅105).
The second line of each test case contains a sequence of n non-negative integers a1,…,an (0≤ai≤109).
It is guaranteed that the sum of n over all test cases does not exceed 3⋅105.
Output
For each test case, output a single line containing “Yes” (without quotes) if it’s possible to make the given array sharpened using the described operations, or “No” (without quotes) otherwise.
题意：给你一堆数字 对于每个数字你可以让该数字无限次减一 最多减为0
问是否可以构造出一个序列 a[0]<a[1]<a[2]<a[3]…<a[k]>a[k+1]>a[k+2]
思路;我们可以对于顺序把第i个数字变化为第i-1 只要这个数字≥i-1即可 不满足跳出来 记该位置为l
对于倒序 我们让第n-i个数 ≥n-i-1 不满足跳出来 记该位置为r
只要l≥r即可
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define me(a,x) memset(a,x,sizeof a)
#define pb(a) push_back(a)
#define pa pair<int,int>
#define fi first
#define se second
int main()
{
int t;cin>>t;
while(t--)
{
int n;cin>>n;
vector<int>a(n);
for(int i=0; i<n; i++)
cin>>a[i];
int l=n,r=-1;
for(int i=0; i<n; i++){
if(a[i]<i) break;
l=i;
}
for(int i=n-1; i>=0; i--){
if(a[i]<n-i-1) break;
r=i;
}
puts(l>=r?"Yes":"No");
}
return 0;
}
C. Mind Control
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
You and your n−1 friends have found an array of integers a1,a2,…,an. You have decided to share it in the following way: All n of you stand in a line in a particular order. Each minute, the person at the front of the line chooses either the first or the last element of the array, removes it, and keeps it for himself. He then gets out of line, and the next person in line continues the process.
You are standing in the m-th position in the line. Before the process starts, you may choose up to k different people in the line, and persuade them to always take either the first or the last element in the array on their turn (for each person his own choice, not necessarily equal for all people), no matter what the elements themselves are. Once the process starts, you cannot persuade any more people, and you cannot change the choices for the people you already persuaded.
Suppose that you’re doing your choices optimally. What is the greatest integer x such that, no matter what are the choices of the friends you didn’t choose to control, the element you will take from the array will be greater than or equal to x?
Please note that the friends you don’t control may do their choice arbitrarily, and they will not necessarily take the biggest element available.
Input
The input consists of multiple test cases. The first line contains a single integer t (1≤t≤1000) — the number of test cases. The description of the test cases follows.
The first line of each test case contains three space-separated integers n, m and k (1≤m≤n≤3500, 0≤k≤n−1) — the number of elements in the array, your position in line and the number of people whose choices you can fix.
The second line of each test case contains n positive integers a1,a2,…,an (1≤ai≤109) — elements of the array.
It is guaranteed that the sum of n over all test cases does not exceed 3500.
Output
For each test case, print the largest integer x such that you can guarantee to obtain at least x.
题意:有n个数 你在第m个位置 现在从第一个人开始 在一个长度为n的序列中，从头或者尾去选取，问你能选取的值x的最大值是多少 你可以控制前k个人 强迫他们选头或者尾
x表示你强迫了k个人选取后，不管剩下人怎么选 你能选到的数都≥x
思路：等于是 你在第m个位置 只要前m-1个人 选完了 你只要选两端的最大值即可
所以 如果k>=m-1的话 意味着你可以控制你前面所有的人 所以枚举i 表示有i个人从头选
m-1-i个人从后面选 那么你能选的就是 max(ans,max(a[i+1],a[n-(m-1-i)]))
如果k＜m-1
我们还是去枚举k
枚举i表示 强迫i个人选择头 那么也就是受强迫的有k-i个人选择尾
然后去枚举剩下不能强迫的人 枚举j 表示不受强迫的有j个人选择头
那么总的来说 就是 i+j个人选择了头 总共选了m-1次 就有m-1-i-j个人选了尾
那么q=min(q,max(a[i+j+1],a[n-(m-1-i-j)]))
里面取最大 是因为该你取了 肯定大的
总的最小 是因为你不能强迫的人 他们不一定怎么选
q是代表 你每次强迫i个人选头的x的值
因为x要取最大
所以答案就是 ans=max(ans,q); 这里取最大是因为 k个可以强迫的人是你可以影响的
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define me(a,x) memset(a,x,sizeof a)
#define pb(a) push_back(a)
#define pa pair<int,int>
#define fi first
#define se second
int main()
{
int t;cin>>t;
while(t--)
{
int n,m,k;cin>>n>>m>>k;
vector<int>a(n+10);
for(int i=1;i<=n;i++) cin>>a[i];
int ans=-1;
if(k>=m-1){
for(int i=0;i<=m-1;i++){
ans=max(ans,max(a[i+1],a[n-(m-1-i)]));
}
}
else
{
for(int i=0;i<=k;i++){
int q=1e9;
for(int j=0;j<=m-1-k;j++){
q=min(q,max(a[i+j+1],a[n-(m-1-i-j)]));
}
ans=max(ans,q);
}
}
cout<<ans<<endl;
}
return 0;
}
京公网安备 11010502036488号