第十九届浙大城市学院程序设计竞赛（同步赛）

比赛中由于没看到I题的数据范围，写了个数状数组优化的LIS，一直写挂了，中途就去打游戏了，最近比较忙…剩余题天梯赛后补

A. Who is The 19th ZUCCPC Champion

思路：输出任意字符串即可

Code：

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl '\n';
typedef long long ll;
typedef pair<ll,ll> PII;
const int N=5e5+10,mod=1e9+7;
int main(){
    IOS;
    cout<<"Ranni the Witch"<<endl;
    return 0;
}

B. Jiubei and Overwatch

思路：显然 $k$ 满足单调性，直接二分即可

Code：

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
typedef pair<int,int> PII;
const int N=1e6+10,mod=1e9+7;
ll n,k,x,y,a[N],maxn;
bool check(ll mid){
    if(mid<=k&&mid*x>=maxn) return true;
    if(mid>k&&(k*x+(mid-k)*y)>=maxn) return true;
    return false;  
}
void wraith(){
    cin>>n>>k>>x>>y;
    maxn=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        maxn=max(maxn,a[i]);
    }
    ll l=1,r=maxn;
    while(l<=r){
        ll mid=(l+r)>>1;
        if(check(mid)) r=mid-1;
        else l=mid+1;
    }
    cout<<l<<endl;
}
int main() {
    int T;
    cin>>T;
    for(int _=1;_<=T;_++) wraith();
    return 0;
}

C. Ah, It’s Yesterday Once More

思路：算法 $1$ 每次执行到 $i$ 时 $[1, i ? 1]$ 必定有序且 $a [i ? 1] = n$ ，相当于 $a [i]$ 向左冒泡到他应该在的位置
对于冒泡排序，它交换的次数等于逆序对数量
因此，直接倒序输出前 $n$ 个数即可

Code：

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
typedef pair<int,int> PII;
const int N=1e6+10,mod=1e9+7;
int n,a[N];
void wraith(){
    cin>>n;
    for(int i=n;i>=1;i--) cout<<i<<" ";
    cout<<endl;
}
int main() {
    int T;
    cin>>T;
    for(int _=1;_<=T;_++) wraith();
    return 0;
}

F. Sum of Numerators

思路：显然奇数位是直接加到结果上的，那么问题就在偶数位，我们来看： $2 + 4 + 6 + ? ? ? + 2 ? i + ? ? ?$ ，显然它们和分母同时约去一个 $2$ 之后又变成了连续的自然数相加，注意每次项数的变化
然后我们再重复上述过程，每次加上奇数的时候就是 $O (1)$ 的等差数列求和，递归的复杂度是 $O (m a x (k, l o g n))$

Code：

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl '\n';
typedef long long ll;
typedef pair<ll,ll> PII;
const int N=5e5+10,mod=1e9+7;
ll t,n,k,ans;
void solve(ll n,ll k){
    while(k){
        if(n==1) {
            ans++;
            break;
        }
        if(n%2==0){
            ans+=n*n/4;
            n/=2;
        }else{
            ans+=(n+1)*(n+1)/4;
            n=n/2;
        }
        k--;
    }
    if(k==0) ans+=(n)*(n+1)/2;
}
int main(){
    IOS;
    cin>>t;
    while(t--){
        ans=0;
        cin>>n>>k;
        solve(n,k);
        cout<<ans<<endl;
    }
    return 0;
}

I. Array Division

思路：考虑 $f [i]$ 表示前 $i$ 个数可以划分的最多段数，则当满足 $\sum\limits_{k=i+1}^{j} a_k\ge\sum\limits_{k=i+1}^{j} b_k$ 时，有转移方程： $f [j] = f [i] + 1$
令 $d_i=\sum\limits_{i=1}^j (a_j-b_j)$ ，问题就转化为了我们要求出从非负位置开始以 $c_n$ 为结尾的最长上升子序列的长度，直接暴力 $d p$ ，复杂度为 $O(n^2)$ ，由于 $\sum n\le5000$ ，因此可以接受
由于比赛时候看漏了这个数据条件，所以，可以用树状数组优化最长上升子序列这个问题，复杂度优化为 $O (n l o g n)$

Code： $O(n^2)$

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
typedef pair<int,int> PII;
const int N=1e6+10,mod=1e9+7;
template<class T>
void read(T &x){
	x=0; char c; int sign=1;
	do{ c=getchar(); if(c=='-') sign=-1;}while(!isdigit(c));
	do{ x=x*10+c-'0',c=getchar();}while(isdigit(c));
	x*=sign;
}
ll n,F[N],a[N],b[N];
void wraith(){
    read(n);
	for(int i=1;i<=n;++i) read(a[i]);
	for(int i=1;i<=n;++i) read(b[i]),a[i]-=b[i];
	for(int i=1;i<=n;++i) a[i]+=a[i-1];
    fill(F+1,F+1+n,-1);
    F[0]=0;
    for(int i=0;i<n;i++){
        if(F[i]==-1) continue;
        for(int j=i+1;j<=n;j++){
            if(a[i]<=a[j]) F[j]=max(F[j],F[i]+1);
        }
    }
    printf("%lld\n",F[n]);
}
int main() {
    int T;
    read(T);
    for(int _=1;_<=T;_++) wraith();
    return 0;
}

Code： $O (n l o g n)$

#include <bits/stdc++.h>
#define ll long long
#define PII pair<ll,ll>
#define MP make_pair
using namespace std;
template<class T>
void read(T &x){
	x=0; char c; int sign=1;
	do{ c=getchar(); if(c=='-') sign=-1;}while(!isdigit(c));
	do{ x=x*10+c-'0',c=getchar();}while(isdigit(c));
	x*=sign;
}
const int N=5e3+50,mod=998244353;
ll T,n,c[N],F[N];
ll a[N],b[N];
void modify(ll p,ll val){
	for(;p<=n;p+=p&-p) c[p]=max(c[p],val);
}
ll ask(ll p){
	ll ret=0;
	for(;p;p-=p&-p) ret=max(ret,c[p]);
	return ret;
}
vector<PII> p;
int main(){
	read(T);
	while(T--){
		read(n);
		for(int i=1;i<=n;++i) read(a[i]);
		for(int i=1;i<=n;++i) read(b[i]),a[i]-=b[i];
		for(int i=1;i<=n;++i) a[i]+=a[i-1];
		for(int i=1;i<=n;++i){
			if(a[i]>=0) p.push_back(MP(a[i],i));
		}
		sort(p.begin(),p.end());
		fill(F+1,F+n+1,0);
        fill(c+1,c+n+1,0);
		for(auto [x,y]:p){
			F[y]=ask(y-1)+1;
			modify(y,F[y]);
		}
		if(F[n]!=0) printf("%lld\n",F[n]);
		else puts("-1");
		p.clear();

	}
	return 0;
}

L. Monster Tower

思路：求满足条件的最小的 $x$ ，显然二分， $c h e c k$ 函数用一个优先队列维护一下即可

Code：

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
typedef pair<int,int> PII;
const int N=1e6+10,mod=1e9+7;
ll n,k,a[N],maxn;
priority_queue<ll,vector<ll>,greater<ll>>q;
bool check(ll x){
    while(!q.empty()) q.pop();
    for(int i=1;i<=k;i++) q.push(a[i]);
    ll pos=k;
    while(!q.empty()){
        if(q.top()>x) return false;
        while(q.top()<=x&&!q.empty()){
            x+=q.top();
            q.pop();
        }
        while(q.size()<k&&pos<n) q.push(a[++pos]);
    }
    return true;
}
void wraith(){
    cin>>n>>k;
    maxn=0;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        maxn=max(maxn,a[i]);
    }
    ll l=0,r=maxn;
    while(l<=r){
        ll mid=(l+r)>>1;
        if(check(mid)) r=mid-1;
        else l=mid+1;
    }
    cout<<l<<endl;
}
int main() {
    int T;
    cin>>T;
    for(int _=1;_<=T;_++) wraith();
    return 0;
}