HZNU Training 2 for Zhejiang Provincial Competition 2020

B - B

题意：给你一个n，m，一个长度为n的01串，有m个1，问你怎么弄，使得有1的区间数最大；

解法：这题偏思维，你直接想1的区间不好想，转换为求全为0的区间，

拿总和-全为0的就是了，问题为n-m个0放到m+1个区间，怎么放；
先令 cnt1=(n-m)/(m+1),表示每个区间的平均0，
然后 cnt2=(n-m)%(m+1),表示剩余的0，那剩余的0怎么放呢？
开始我想放在两边，但这样是不对的，应该继续插在中间的区间放，
那这样的话中间区间数为 getsum(cnt1)*(m+1)
加上剩余的 cnt2*(cnt1+1)；
这算是正难则反的思想的体现吧；主要是没想到分开区间来放。

#include<cstdio>
#include<cstring>
#include<stack>
using namespace std;
typedef long long ll;
const int N=2e3+5;
ll getsum(ll x){return x*(x+1)/2;}
int main(){
      int t;
      scanf("%d",&t);
    while(t--){
    ll n,m;
    scanf("%lld %lld",&n,&m);
    ll tot=getsum(n);
    ll cnt1=(n-m)/(m+1);
    ll cnt2=(n-m)%(m+1);
    ll ans=tot-getsum(cnt1)*(m+1)-cnt2*(cnt1+1);
    printf("%lld
",ans);
    }
    return 0;
}

View Code

C - C

Gym - 102411M

题意：一个序列，问你有多少个 a[j]-a[i]=a[k]-a[j] $a_{k} - a_{j} = a_{j} - a_{i}$

$a_{k} - a_{j} = a_{j} - a_{i}$

#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++)
#define per(i,j,k) for(int i=(int)k;i>=(int)j;i--)
#define pb push_back
#define pf push_front
#define fi first
#define se second 11
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef double db;
// const db PI=acos(-1.0);
const ll INF=0x3f3f3f3f3f3f3f3fLL;
const int inf=0x3f3f3f3f;//0x7fffffff;
const double eps=1e-9;
const ll MOD=9999991;
const int maxn=2e3+5;
ll a[maxn];
int main(){
    int n,t;
    scanf("%d",&t);
    while(t--){
    unordered_map<ll,ll>mp;
    int ans=0;
    scanf("%d",&n);
    for(int k=1;k<=n;k++){
    scanf("%lld",&a[k]);
    ans+=mp[a[k]];
    for(int i=1;i<k;i++)mp[2*a[k]-a[i]]++;
    }
    printf("%d
",ans);
    } 
     // system("pause");
    a[j]-a[i]=a[k]-a[j];
    a[k]=2*a[j]-a[i];
    return 0;
}

View Code

F - F

$a_{k} - a_{j} = a_{j} - a_{i}$

题意：给你一个01串，我也不知道为什么出题喜欢01串，一共可以跳k步，使得这个值最小。
解法：一开始用O(n^2)的算法，但这是过不了的，然后开始优化，也没想出个门道。
正确的做法是这样的：用一个head 表示能到的最近的1，
若 k>=i-head，那直接跳过去，让head++，为什么head++是正确的呢？因为是向后枚举的
不可能head++这个位置是0，是0直接换掉了；
若 k<=i-head;就跳i-k个位置。会不会i-k那个位置是0呢？
这可以推出矛盾，如果i-k那个位置为0，那直接跳最近的1不就行了吗，那不就是满足条件1吗；

#include<bits/stdc++.h>
#include<cstdio>
#include<stack>
using namespace std;
#define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++)
#define per(i,j,k) for(int i=(int)k;i>=(int)j;i--)
#define pb push_back
#define pf push_front
#define fi first
#define se second 11
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef double db;
// const db PI=acos(-1.0);
const ll INF=0x3f3f3f3f3f3f3f3fLL;
const int inf=0x3f3f3f3f;//0x7fffffff;
const double eps=1e-9;
const ll MOD=9999991;
const int maxn=1e6+5;
// ll a[maxn];
char s[maxn];
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
     ll n,k;
    scanf("%lld %lld",&n,&k);
    string s;
    cin>>s;
    ll head=0;
    while(s[head]=='0')head++;
    for(ll i=head;i<n;i++){
    if(k<=0)continue;
    if(s[i]=='0'){
    if(k>=i-head)swap(s[i],s[head]),k-=(i-head),head++;
    else if(i-k>=0){
    swap(s[i],s[i-k]);
    k=0;
    }
    
    }

    }
    cout<<s<<endl;
    }
   // system("pause");
    return 0;
}

View Code

H - H

HDU - 5974

题意：x+y=a,lcm(x,y)=b;让你求x，y；

做法：写了一次穷举，然后T；

正解：

可能这就是数论的巧妙之处吧；

#include<cstdio>
#include<cmath>
using namespace std;
#define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++)
#define per(i,j,k) for(int i=(int)k;i>=(int)j;i--)
#define pb push_back
#define pf push_front
#define fi first
#define se second 11
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef double db;
// const db PI=acos(-1.0);
const ll INF=0x3f3f3f3f3f3f3f3fLL;
const int inf=0x3f3f3f3f;//0x7fffffff;
const double eps=1e-9;
const ll MOD=9999991;
const int maxn=2e3+5;
// ll a[maxn];
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
int main(){
      ll a,b;
      while(~scanf("%lld %lld",&a,&b)){
      ll  c=gcd(a,b);
      ll d=a*a-4*b*c;
      if(d<0){
        printf("No Solution
");
      continue;
      }
      ll i=(a-sqrt(d))/2/c;
      ll j=a/c-i;
      ll x=c*i,y=c*j;
      if(x*y/c==b)printf("%lld %lld
",x,y);
     else    printf("No Solution
");

      }
    return 0;
}

View Code

$1 \leq i < j < k \leq n$

想的太多，做的太少；