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

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

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

A. Who is The 19th ZUCCPC Champion

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

Code：

#include 
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 k k满足单调性，直接二分即可

Code：

#include 
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 1 1每次执行到 i i i时 [ 1 , i − 1 ] [1,i-1] [1,i−1]必定有序且 a [ i − 1 ] = n a[i-1]=n a[i−1]=n，相当于 a [ i ] a[i] a[i]向左冒泡到他应该在的位置
对于冒泡排序，它交换的次数等于逆序对数量
因此，直接倒序输出前 n n n个数即可

Code：

#include 
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+4+6+···+2*i+··· 2+4+6+⋅⋅⋅+2∗i+⋅⋅⋅，显然它们和分母同时约去一个 2 2 2之后又变成了连续的自然数相加，注意每次项数的变化
然后我们再重复上述过程，每次加上奇数的时候就是 O ( 1 ) O(1) O(1)的等差数列求和，递归的复杂度是 O ( m a x ( k , l o g n ) ) O(max(k,logn)) O(max(k,logn))

Code：

#include 
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 ] f[i] f[i]表示前 i i i个数可以划分的最多段数，则当满足 ∑ k = i + 1 j a k ≥ ∑ k = i + 1 j b k \sum\limits_{k=i+1}^{j} a_k\ge\sum\limits_{k=i+1}^{j} b_k k=i+1∑j​ak​≥k=i+1∑j​bk​时，有转移方程： f [ j ] = f [ i ] + 1 f[j]=f[i]+1 f[j]=f[i]+1
令 d i = ∑ i = 1 j ( a j − b j ) d_i=\sum\limits_{i=1}^j (a_j-b_j) di​=i=1∑j​(aj​−bj​)，问题就转化为了我们要求出从非负位置开始以 c n c_n cn​为结尾的最长上升子序列的长度，直接暴力 d p dp dp，复杂度为 O ( n 2 ) O(n^2) O(n2)，由于 ∑ n ≤ 5000 \sum n\le5000 ∑n≤5000，因此可以接受
由于比赛时候看漏了这个数据条件，所以，可以用树状数组优化最长上升子序列这个问题，复杂度优化为 O ( n l o g n ) O(nlogn) O(nlogn)

Code： O ( n 2 ) O(n^2) O(n2)

#include 
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 ) O(nlogn) O(nlogn)

#include 
#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 x x，显然二分， c h e c k check check函数用一个优先队列维护一下即可

Code：

#include 
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;
}