当前位置：首页 > news >正文

CSU-ACM2018寒假集训选拔-入门题

news 来源：原创 2024/5/9 2:16:15

【题目链接】：http://vj.bit-studio.cn/contest/205664#overview

A：

【给你一个长度为n的序列，尾部插入再反转，求n次后最终序列】【规律/思维】

【分析】：STL-deque会超时，只能找规律。

【代码】：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+7;
int a[maxn],ans[maxn];
int n;
int main()
{
   scanf("%d",&n);
   for(int i=1;i<=n;i++){
    scanf("%d",&a[i]);
   }
   int l=1,r=n,k=n,cnt=1;
   for(int i=n;i>=1;i--){
        if(cnt&1)
            ans[l++]=a[k--];
        else
            ans[r--]=a[k--];
        cnt++;
   }
   for(int i=1;i<=n-1;i++)
    printf("%d ",ans[i]);
   printf("%d\n",ans[n]);
}
/*
1 2 3 4
4 2 1 3

0   6  7  6 7 0
n-2 3 n-1 2 n 1
↓
0 6 6 0 7 7
*/

规律

【将长度为n的序列分为两部分，满足这两部分差值的绝对值最小】【前缀和】

【分析】：求出前缀和，然后打擂台求某部分前缀和sum[i]和n-sum[i]的差值abs最小值，注意防爆int。

【代码】：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int maxn = 2e5+100;
LL a[maxn],sum[maxn],tot;
LL Min = 1000000000000000000LL;
int n;
int main()
{
   scanf("%d",&n);
   for(int i=1;i<=n;i++){
    scanf("%lld",&a[i]);
    sum[i]=sum[i-1]+a[i];
    tot+=a[i];
   }
   for(int i=1;i<n;i++){
    Min=min(Min,abs(2*sum[i]-tot));
   }
   printf("%lld\n",Min);
}

前缀和

【判断重排后的序列是否能够相邻元素乘积为4的倍数】【规律/思维】

【分析】：分成4的倍数，2的倍数，奇数。只要奇数和4的倍数可以交叉相邻即可。

【代码】：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int maxn = 2e5+100;
int a[maxn],cnt1,cnt2,cnt4;
int n;
int main()
{
   scanf("%d",&n);
   for(int i=1;i<=n;i++){
    scanf("%d",&a[i]);
    if(a[i]%4==0) cnt4++;
    else if(a[i]%2==0) cnt2++;
    else cnt1++;
   }
   if(cnt1>cnt4+1 || (cnt2 && (cnt1==cnt4+1)))
    puts("No");
   else puts("Yes");

}

规律

D：

【类似蛇形填数】【模拟】

【代码】：

E：

【区间相交长度】【贪心】

【分析】：选取b/d较小-a/c较大，不小于0输出，否则说明不相交输出0

【代码】：

#include <bits/stdc++.h>

using namespace std;

#define MP make_pair
#define PB push_back
typedef long long LL;
typedef pair<int,int> PII;
const double eps=1e-8;
const double pi=acos(-1.0);
const int K=1e6+7;
const int mod=1e9+7;

int a,b,c,d;
LL ans;
int main()
{
    cin>>a>>b>>c>>d;
    ans=min(b,d)-max(a,c);
    if(ans<0) ans=0;
    cout<<ans<<'\n';
    return 0;
}