A:
因为保证是奇数,所以先拿掉最多的那个球的一个,剩下的球总和是偶数,且保证能互相抵消
for _ in range(int(input())):
x=int(input())
a=list(map(int,input().split()))
print(a.index(max(a))+1)
B:
最大值肯定n-1+n,所以保证倒数第三个要清成0,所以倒数第四个是n-2,保证了比1大
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
int t;
cin>>t;
int n;
while(t--){
cin>>n;
for(int i=n-3;i>1;i--) cout<<i<<" ";
cout<<n-2<<" "<<1<<" "<<n-1<<" "<<n<<endl;;
}
}
C:
贪心,最大的只能变小,
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 2e5+10;
int n;
int count(int x){
int res=0;
while(x) res++,x/=10;
return res;
}
int main()
{
int t;
cin>>t;
while(t--)
{
cin>>n;
priority_queue<int,vector<int>,less<int>> a,b;
for(int i=1;i<=n;i++){
int x;
cin>>x;
a.push(x);
}
for(int i=1;i<=n;i++){
int x;
cin>>x;
b.push(x);
}
int cnt=0;
while(a.size()){
int x=a.top();a.pop();
int y=b.top();b.pop();
if(x==y) continue;
else if(x>y){
x=count(x);
a.push(x);
b.push(y);
}
else{
y=count(y);
b.push(y);
a.push(x);
}cnt++;
}
cout<<cnt<<endl;
}
}
D:
最优策略下只能alice赢,所以保证不打平就行,打平的情况只有两个,回文字符(这里保证原字符串是偶数)和bbbbaa这种情况,区间dp参考了的写法,
#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <vector>
#include <map>
const int N = 2e3 + 10;
const int INF = 0x7f7f7f7f;
int dp[N][N];
std::string s;
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int T;
std::cin >> T;
while (T--)
{
memset(dp, 0, sizeof dp);
std::cin >> s;
int n = s.size();
s = "?" + s;
for (int i = 1; i <= n - 1; ++i)
if (s[i] != s[i + 1])
dp[i][i + 1] = 1;
else
dp[i][i + 1] = 0;
for (int len = 2; len <= n; len += 2)
{
for (int l = 1; l + len - 1 <= n; ++l)
{
int r = l + len - 1;
//dp[r-1][r]
if ((dp[l][r - 2] ||dp[r-1][r]) && (dp[l + 1][r - 1] ||s[l]!=s[r]))
// 先手拿r,枚举后手拿r-1或l
dp[l][r] = 1;
else if ((dp[l + 2][r] || dp[l][l+1]) && (dp[l + 1][r - 1] || s[l]!=s[r]))
// 先手拿l,枚举后手拿l+1或r
dp[l][r] = 1;
else
dp[l][r] = 0;
}
}
if (dp[1][n])
std::cout << "Alice" << '\n';
else
std::cout << "Draw" << '\n';
}
return 0;
}
第二种:
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 2e5+10;
int n;
int count(int x){
int res=0;
while(x) res++,x/=10;
return res;
}
int main()
{
int t;
cin>>t;
while(t--){
string s;
cin>>s;
int l=0;
int r=s.size()-1;
while(s[l]==s[r]) l++,r--;
int a=0;
for(int i=l;i<r;i+=2)
if(s[i]!=s[i+1]) a=1;
cout<<(a?"Alice":"Draw")<<endl;
}
}
E
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int N =3e5+10,P=13331;
typedef long long LL;
LL s[N];
LL sum;
LL tmp[N];
int n,m;
void merge_sort(LL q[], int l, int r)
{
if(l>=r) return ;
int mid=l+r>>1;
merge_sort(q,l,mid);
merge_sort(q,mid+1,r);
int i=l,j=mid+1,k=0;
while(i<=mid&&j<=r){
if(q[i]<=q[j]) tmp[k++]=q[i++];
else tmp[k++]=q[j++];
}
while(i<=mid) tmp[k++]=q[i++];
while(j<=r) tmp[k++]=q[j++];
for(i=l,j=0;i<=r;i++,j++)
q[i]=tmp[j];
}
int main()
{
scanf("%d", &n);
for(int i=1;i<=n;i++){
int a,b;
scanf("%d%d", &a, &b);
sum+=a;//先全选a
s[i]=-(b-a);//意思是当前菜盘选b不选a,因为要从大到小排序所以直接给了个-号
//这里就是如果选b不选a会损失or得到多少
}
merge_sort(s,1,n);
for(int i=1;i<=n;i++)
s[i]+=s[i-1];//枚举搭配意思就是i=1的时候第一个菜盘选b不选a
//i=2的时候,第一和第二菜盘都选b不选a(注意这里是无序的,不一定是这个意思)
scanf("%d", &m);
unordered_map<LL,LL> mp;
//这里用了哈希的散列,P=13331了,冲突概率很低(131会wa)
while (m -- ){
int x,y;
scanf("%d%d", &x, &y);
if(mp.find(1ll*x*P+y)!=mp.end())
printf("%lld\n",mp[1ll*x*P+y]);
else{
LL res=-1;
if(x<=y){//这里纯优化.... 毕竟枚举大的另一个数的k就会少
for(int i=0;i<=n;i+=y){
if((n-i)%x==0)//枚举 n-i*y=kx的k
res=max(res,sum-s[i]);//减去选了多少个i的y
}
}
else{
for(int i=0;i<=n;i+=x){
if((n-i)%y==0){
res=max(res,sum-s[n-i]);
}
}
}
mp[1ll*x*P+y]=res;
printf("%lld\n",res);
}
}
}