problem A
题意
Let LCM(x,y) be the minimum positive integer that is divisible by both x and y. For example, LCM(13,37)=481, LCM(9,6)=18.
You are given two integers l and r. Find two integers x and y such that l≤x<y≤r and l≤LCM(x,y)≤r.
Input
The first line contains one integer t (1≤t≤10000) — the number of test cases.
Each test case is represented by one line containing two integers l and r (1≤l<r≤109).
Output
For each test case, print two integers:
if it is impossible to find integers x and y meeting the constraints in the statement, print two integers equal to −1;
otherwise, print the values of x and y (if there are multiple valid answers, you may print any of them).
思路
贪心就好了，我们可以知道l*2是最小的我们可以找到的可以和l组成最小公倍数的数字，我们直接找这个数字就好了。
problem B
题意
You are given an array a1,a2,…,an, consisting of n positive integers.
Initially you are standing at index 1 and have a score equal to a1. You can perform two kinds of moves:
move right — go from your current index x to x+1 and add ax+1 to your score. This move can only be performed if x<n.
move left — go from your current index x to x−1 and add ax−1 to your score. This move can only be performed if x>1. Also, you can't perform two or more moves to the left in a row.
You want to perform exactly k moves. Also, there should be no more than z moves to the left among them.
What is the maximum score you can achieve?
Input
The first line contains a single integer t (1≤t≤104) — the number of testcases.
The first line of each testcase contains three integers n,k and z (2≤n≤105, 1≤k≤n−1, 0≤z≤min(5,k)) — the number of elements in the array, the total number of moves you should perform and the maximum number of moves to the left you can perform.
The second line of each testcase contains n integers a1,a2,…,an (1≤ai≤104) — the given array.
The sum of n over all testcases does not exceed 3⋅105.
Output
Print t integers — for each testcase output the maximum score you can achieve if you make exactly k moves in total, no more than z of them are to the left and there are no two or more moves to the left in a row.
思路
由于我们不能连续往左走，所以说我们最优的策略一定是在这组数据的相邻两项里面来回游走。那么我们需要记录的就是相邻两项的和，并且记录一个前缀和表示不往回走的值，然后我们找到小于右端点的最大的相邻两数，然后加上最多可以走的次数，和右端点的前缀和取一个max就是答案了。
代码实现
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
#define rep(i,f_start,f_end) for (int i=f_start;i<=f_end;++i)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define MT(x,i) memset(x,i,sizeof(x) )
#define rev(i,start,end) for (int i=start;i<end;i++)
#define inf 0x3f3f3f3f
#define mp(x,y) make_pair(x,y)
#define lowbit(x) (x&-x)
#define MOD 1000000007
#define exp 1e-8
#define N 1000005
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef vector <int> VI;
typedef pair<int ,int> PII;
typedef pair<int ,PII> PIII;
ll gcd (ll a,ll b) {return b?gcd (b,a%b):a; }
inline int read() {
char ch=getchar(); int x=0, f=1;
while(ch<'0'||ch>'9') {
if(ch=='-') f = -1;
ch=getchar();
}
while('0'<=ch&&ch<='9') {
x=x*10+ch-'0';
ch=getchar();
} return x*f;
}
const int maxn=1e5+10;
int a[maxn];
int sum[maxn];
ll v[maxn];
int t;
int n,k,z;
int main() {
cin>>t;
while (t--) {
scanf ("%d%d%d",&n,&k,&z);
rep (i,1,n) {
scanf ("%d",&a[i]);
sum[i]=sum[i-1]+a[i];
}
rev (i,1,n) v[i]=a[i]+a[i+1];
ll ans=sum[k+1],ed=k+1,m=-1;
rep (j,1,z) {
ed=k+1-2*j;
m=-1;
if (ed<1) break;
rep (i,1,ed) m=max (m,v[i]);
ans=max (sum[ed]+m*j,ans);
}
cout<<ans<<endl;
}
return 0;
}
problem C
题意
Let's call left cyclic shift of some string t1t2t3…tn−1tn as string t2t3…tn−1tnt1.
Analogically, let's call right cyclic shift of string t as string tnt1t2t3…tn−1.
Let's say string t is good if its left cyclic shift is equal to its right cyclic shift.
You are given string s which consists of digits 0–9.
What is the minimum number of characters you need to erase from s to make it good?
Input
The first line contains single integer t (1≤t≤1000) — the number of test cases.
Next t lines contains test cases — one per line. The first and only line of each test case contains string s (2≤|s|≤2⋅105). Each character si is digit 0–9.
It's guaranteed that the total length of strings doesn't exceed 2⋅105.
Output
For each test case, print the minimum number of characters you need to erase from s to make it goo
思路
首先，我们简单分析就可以得出，题目所说的牛逼串肯定是只有一种字母或者两种字母组成，超出两种那么无论如何都无法组成牛逼串，那么两种的话一定是穿插组成。那么我们记录每个字母出现的位置和次数，暴力枚举就好了。
代码实现
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
#define rep(i,f_start,f_end) for (int i=f_start;i<=f_end;++i)
#define per(i,n,a) for (int i=n;i>=a;i--)
#define MT(x,i) memset(x,i,sizeof(x) )
#define rev(i,start,end) for (int i=start;i<end;i++)
#define inf 0x3f3f3f3f
#define mp(x,y) make_pair(x,y)
#define lowbit(x) (x&-x)
#define MOD 1000000007
#define exp 1e-8
#define N 1000005
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef vector <int> VI;
typedef pair<int ,int> PII;
typedef pair<int ,PII> PIII;
ll gcd (ll a,ll b) {return b?gcd (b,a%b):a; }
inline int read() {
char ch=getchar(); int x=0, f=1;
while(ch<'0'||ch>'9') {
if(ch=='-') f = -1;
ch=getchar();
}
while('0'<=ch&&ch<='9') {
x=x*10+ch-'0';
ch=getchar();
} return x*f;
}
const int maxn=2e5+10;
int t;
int main() {
cin>>t;
while (t--) {
string s;
cin>>s;
vector <VI> pos(10);
rev (i,0,s.length ()) {
int x=s[i]-'0';
pos[x].pb (i);
}
int ans=0;
rev (i,0,10) ans=max (ans, (int) pos[i].size ());
rev (i,0,10) {
rev (j,0,10) {
if (i==j) continue;
int cnt=0;
int l=0,r=0,pre=-1;
while (l<pos[i].size()&&r<pos[j].size ()) {
if (pos[i][l]<pos[j][r]&&pos[i][l]>pre) {
cnt+=2;
pre=pos[j][r];
l++,r++;
}
else if (pos[i][l]>pos[j][r]) r++;
else ++l;
}
ans=max (ans,cnt);
}
}
cout<<(int ) s.length ()-ans<<endl;
}
return 0;
}