A. Game with Integers
题意：
两人轮流操作，可以加一或减一，若结果能被3整除则输出First，否则输出Second
思路：
若n不能被3整除，则第一个人可以直接通过加一或减一使结果被3整除，反之则一定不能
代码：
#include <bits/stdc++.h>
using namespace std ;
const int MAXN=1e5+7;
const int INF = 0x3f3f3f3f;
typedef long long ll;
#define endl "\n"
void solve(){
int n;
cin>>n;
if(n%3!=0){
cout<<"First"<<endl;
}else{
cout<<"Second"<<endl;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
B. 250 Thousand Tons of TNT
题意：
将n个盒子按顺序分成若干组，每组都正好k个盒子，求每组的总质量的最大值和最小值的差值
思路：
先求盒子质量的前缀和，再枚举k的值
代码：
#include <bits/stdc++.h>
using namespace std ;
const int MAXN=1e5+7;
const long long INF = 0x3f3f3f3f3f3f3f3f;
typedef long long ll;
#define endl "\n"
void solve(){
int n;
cin>>n;
ll a[n+1];
ll presum[n+1];
presum[0]=0;
for(int i=1;i<=n;i++){
cin>>a[i];
presum[i]=presum[i-1]+a[i];
}
ll ans=0;
for(int i=1;i<n;i++){
if(n%i!=0){
continue;
}
ll maxn=0;
ll minx=INF;
ll num;
for(int j=1+i-1;j<=n;j+=i){
num=presum[j]-presum[j-i];
maxn=max(maxn,num);
minx=min(minx,num);
}
ans=max(ans,maxn-minx);
}
cout<<ans<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
C. Yarik and Array
题意：
给定一个长度为n的数组，求最大相邻子序列和，要求相邻子序列中的相邻元素奇偶性不同
思路：
动态规划，dp[i]表示以第i个元素为结尾的子序列的和的最大值，转移方程为：若第i个元素和前一个数奇偶性一致，则dp[i]=a[i]；若不一致，则dp[i]=max(a[i],dp[i-1]+a[i])。输出最大的dp[i]
代码：
#include <bits/stdc++.h>
using namespace std ;
const int MAXN=1e5+7;
const int INF = 0x3f3f3f3f;
typedef long long ll;
#define endl "\n"
void solve(){
int n;
cin>>n;
ll a[n+1];
for(int i=1;i<=n;i++){
cin>>a[i];
}
ll dp[n+1];
memset(dp,0,sizeof(dp));
ll ans=0;
dp[1]=a[1];
ans=dp[1];
for(int i=2;i<=n;i++){
if((abs(a[i])%2)+(abs(a[i-1])%2)==1){
dp[i]=max(a[i],dp[i-1]+a[i]);
ans=max(ans,dp[i]);
}else{
dp[i]=a[i];
ans=max(ans,dp[i]);
}
}
cout<<ans<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
D. Yarik and Musical Notes
题意：
给定一个长度为n的数组a，b[i]为2a[i] ，若b[i]b[j]=b[j]b[i]，则为一对组合，求这样的组合有多少对
思路：
b[i]b[j]=b[j]b[i]化简后可以得到2a[j]/a[j]=2a[i]/a[i]，若a[i]为2的倍数，则可以与2a[i]进行通分化简，化简后为2x/y，x和y的值是确定的，若(x,y)相同，则肯定是一对组合，反之则肯定不是，所以只需要对数组a进行遍历，看a[i]前面有几个元素和a[i]的(x,y)相同即可
代码：
#include <bits/stdc++.h>
using namespace std ;
const int MAXN=1e5+7;
const int INF = 0x3f3f3f3f;
typedef long long ll;
#define endl "\n"
struct node {
int x,y;
bool operator<(const node& other) const {
return std::tie(x, y) < std::tie(other.x, other.y);
}
};
long long ksm(long long a, long long b)
{
long long res = 1;
while(b)
{
if(b & 1)
res = res * a ;
a = a * a ;
b >>= 1;
}
return res;
}
int check(int t){
int count=0;
while(t>0){
if(t%2!=0){
return count;
}
t/=2;
count++;
}
return count;
}
void solve(){
int n;
cin>>n;
ll a[n+1];
for(int i=1;i<=n;i++){
cin>>a[i];
}
map<node ,int > mp;
ll ans=0;
for(int i=1;i<=n;i++){
int num=check(a[i]);
if(num!=0){
node st;
st.x=a[i]-num;
st.y=a[i]/ksm(2,num);
if(mp[st]>0){
ans+=mp[st];
}
mp[st]++;
}else{
node st;
st.x=a[i];
st.y=a[i];
if(mp[st]>0){
ans+=mp[st];
}
mp[st]++;
}
}
cout<<ans<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
E. Queue Sort
题意：
要对一个数组进行排序，你可以进行以下操作：将第一个元素放在数组最后，将这个元素与前面的元素进行比较并交换，直到这个元素严格大于前面的元素。若不能完成排序则输出-1，否则输出操作次数
思路：
若操作的元素为最小的元素，则在操作后它会回到第一位，形成死循环，所以最小的元素后面的元素必须是已经排好序的，否则输出-1，最小元素前面有几个数则需要操作几次
代码：
#include <bits/stdc++.h>
using namespace std ;
const int MAXN=1e5+7;
const long long INF = 0x3f3f3f3f3f3f3f3f;
typedef long long ll;
#define endl "\n"
void solve(){
int n;
cin>>n;
ll a[n+1];
for(int i=1;i<=n;i++){
cin>>a[i];
}
a[0]=0;
ll low=INF;
int lownum=0;
int flag=1;
for(int i=1;i<=n;i++){
if(a[i]<low){
low=a[i];
lownum=i;
flag=1;
continue;
}
if(a[i]<a[i-1]){
flag=0;
}
}
if(flag==0){
cout<<-1<<endl;
}else{
cout<<lownum-1<<endl;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
while(t--){
solve();
}
return 0;
}
F. Alex's whims
思路：
一开始构造一条链，每次操作根据需要将这条链转化为对应的Y字形。
暂时没想出来如何实现………