Educational Codeforces Round 85 (Rated for Div. 2)

A.Level Statistics
给n个时间递增的值,分别为游戏数和获胜数,判断是否正确。
首先游戏数和获胜数都是递增的,且获胜数不能超过游戏数,同时2个时间的增长的量也不能超过

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
const int N=1e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
int a[N],b[N];
void work()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i],&b[i]);
    }
    for(int i=1;i<=n;i++){
        if(a[i]<b[i]){
            printf("NO\n");return;
        }
    }
    for(int i=2;i<=n;i++){
        if(a[i]-a[i-1]<b[i]-b[i-1]){
            printf("NO\n");return;
        }
        if(a[i]<a[i-1]||b[i]<b[i-1]){
            printf("NO\n");return;
        }
    }
    printf("YES\n");
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

B.Middle Class
有n个数,可以任取任意数将其平均,问最多能有多少个数超过k。
从大到小加,然后判断平均数即可。

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
const int N=1e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
int a[N];
void work()
{
    int n,x;
    scanf("%d%d",&n,&x);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    sort(a+1,a+n+1);
    ll sum=0;
    for(int i=n;i>=1;i--){
        sum+=a[i];
        if(sum/(n-i+1)<x){
            printf("%d\n",n-i);return;
        }
    }
    printf("%d\n",n);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

C.Circle of Monsters
有n个怪物,杀死第i个怪物要\(a_i\)点伤害,第i个怪物死亡会对第i+1个怪物造成\(b_i\)点伤害,第n个对第1个,可以花费1的代价对某个怪物造成1点伤害,问最少要花费多少代价杀死所有怪物。
如果我们选定了从哪个怪物开始杀,那么肯定是从这个怪物开始往后杀下去才是更优的。那么除了我们选定的这个怪物,其他怪物都会受到上一个怪物死亡造成的伤害。那么我们可以先默认每个怪物都受到了上一个怪物的伤害,求和,然后求一个如果从这个怪物开始需要额外花费的最小值。

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
const int N=3e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
ll a[N];
ll b[N];
void work()
{
    ll minn=1e15;
    ll sum=0;
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&a[i],&b[i]);
    }
    for(int i=2;i<=n;i++){
        sum+=max(0ll,a[i]-b[i-1]);
        minn=min(minn,a[i]-max(0ll,a[i]-b[i-1]));
    }
    sum+=max(0ll,a[1]-b[n]);
    minn=min(minn,a[1]-max(0ll,a[1]-b[n]));
    printf("%lld\n",sum+minn);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

D.Minimum Euler Cycle
给一张n个点的完全有向图,要求构造一个字典序最小的路径,恰好走过所有边1次,问第l到第r步 走到哪里。
n为5时 路径为1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5 1,然后分块枚举即可。

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
const int N=3e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
void work()
{
    ll n,l,r;
    scanf("%lld%lld%lld",&n,&l,&r);
    ll now=1;
    for(int i=1;i<=n;i++){
        if(now+2*(n-i)<=l){
            now+=2*(n-i);continue;
        }
        for(int j=i+1;j<=n;j++){
            if(now>=l&&now<=r){
                printf("%d ",i);
            }
            now++;
            if(now>=l&&now<=r){
                printf("%d ",j);
            }
            now++;
            if(now>r){
                printf("\n");return;
            }
        }
    }
    if(now<=r){
        printf("1\n");
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

E.Divisor Paths
给定D,然后给一张含有所有D的因数的图,然后图中x,y有边的要求为x/y为一个素数,边权为是x的因子但不是y的因子的因子数量,给q个询问,问x,y之间的最短路有多少条,模998244353。
解 首先考虑如果x,y不互质,那么显然可以将x,y除掉他们的gcd,变成新的x,y,答案是相同的。那么我们得到的x,y都是互质的,那么意味着,最短路一定经过1(就是一定是先减再增的,不太好证明,自己写几组看看就知道了),然后我们发现对于每个点 他到1的所有路径(点值递减)长度都相同(长度为这个值的因子数),那么就是求这个点到1有多少种路径。然后对于与x相连的所有点(比x小的),都是x去掉一个质因数之后的值,那么可以理解为,每一条路都是x的质因数的一种排列,每往回一个点相当于删除当前排列的最后一个数,那么数量的答案就是质因数的全排列,公式是\(A_n^n/(A_{k1}^{k1}*A_{k2}^{k2}……)\),n为质因数的数量,k为第i种质因数的数量(这个应该高中就学过了,存在相同的数的时候全排列数量)。然后将x,y到1的最短路径的数量乘起来就是答案。
我的写法是直接dfs预处理出所有值到1的数量,然后qlog求解(358ms)。
hjt的写法为预处理出D的所有质因数,然后在询问中再求解,复杂度一样,但是常数大一点。2个代码都在下面贴出。(gyz和他相同的做法,然后一个1279ms,一个421ms)

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
const int N=3e5+5;
const int p=998244353;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
vector<pair<ll,int> >v;
map<ll,ll>m;
void dfs(int now,ll tmp,ll sum,ll ans)
{
    //printf("%lld %lld\n",tmp,ans);
    m[tmp]=ans;
    if(now==v.size())return;
    for(int i=0;i<=v[now].sc;i++){
        if(i>=1){
            tmp*=v[now].fr;
            ans=(ans*(sum+i)%p*qpow(i,p-2)%p);
        }
        dfs(now+1,tmp,sum+i,ans);
    }
}
void work()
{
    ll D;
    scanf("%lld",&D);
    for(ll i=2;i*i<=D;i++){
        if(D%i==0){
            int cnt=0;
            while(D%i==0){
                D/=i;
                cnt++;
            }
            pair<ll,int>p;
            p.fr=i;
            p.sc=cnt;
            v.push_back(p);
        }
    }
    if(D!=1){
        v.push_back(make_pair(D,1));
    }
    dfs(0,1,0,1);
    int q;
    scanf("%d",&q);
    for(int i=1;i<=q;i++){
        ll x,y;
        scanf("%lld%lld",&x,&y);
        if(x<y)swap(x,y);
        ll tmp=__gcd(x,y);
        x/=tmp;
        y/=tmp;
        printf("%lld\n",m[x]*m[y]%p);
    }
 
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

hjt的

#include <bits/stdc++.h>
using namespace std;
#define repeat(i,a,b) for(int i=(a),_=(b);i<_;i++)
#define repeat_back(i,a,b) for(int i=(b)-1,_=(a);i>=_;i--)
#define mst(a,x) memset(a,x,sizeof(a))
#define vector basic_string
#define fi first
#define se second
#ifndef qwq
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
#endif
//mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const int N=300010; const double err=1e-11; typedef long long ll; const int inf=~0u>>2; const ll INF=~0ull>>2; ll read(){ll x; if(scanf("%lld",&x)==-1)exit(0); return x;} typedef double lf; typedef long double llf; const lf pi=acos(-1.0); lf readf(){lf x; if(scanf("%lf",&x)==-1)exit(0); return x;} template<typename T> T sqr(const T &x){return x*x;} typedef pair<int,int> pii; template<typename A,typename B> ostream &operator<<(ostream &o,const pair<A,B> &x){return o<<'('<<x.fi<<','<<x.se<<')';}
const int mod=(0?1000000007:998244353); ll mul(ll a,ll b,ll m=mod){return a*b%m;} ll qpow(ll a,ll b,ll m=mod){ll ans=1; for(;b;a=mul(a,a,m),b>>=1)if(b&1)ans=mul(ans,a,m); return ans;} ll getinv(ll v,ll m=mod){return qpow(v,m-2,m);}
#define int ll
int T,n,l,r,rr;
vector<int> d;
map<int,vector<int>> a;
struct CC{
	static const int N=1010;
	ll fac[N],inv[N];
	CC(){
		fac[0]=1;
		repeat(i,1,N)fac[i]=fac[i-1]*i%mod;
		inv[N-1]=qpow(fac[N-1],mod-2,mod);
		repeat_back(i,0,N-1)inv[i]=inv[i+1]*(i+1)%mod;
	}
}C;
void getdivisor(vector<int> &ans,int n){
	ans.assign(d.size(),0);
	repeat(i,0,d.size())
	while(n%d[i]==0)n/=d[i],ans[i]++;
}
vector<int> X,Y;
signed main(){
	int n=read(),q=read();
	for(int i=2;i*i<=n;i++){
		if(n%i==0)d.push_back(i);
		while(n%i==0)n/=i;
	}
	if(n>1)d.push_back(n);
	//orzeach(d);
	while(q--){
		int x=read(),y=read();
		getdivisor(X,x);
		getdivisor(Y,y);
		
		int ans1=1,ans2=1,sum=0;
		repeat(i,0,d.size())
		if(X[i]>Y[i])
			ans2=ans2*C.inv[abs(X[i]-Y[i])]%mod,
			sum+=abs(X[i]-Y[i]);
		ans1=ans1*C.fac[sum]%mod;
		
		sum=0;
		repeat(i,0,d.size())
		if(X[i]<Y[i])
			ans2=ans2*C.inv[abs(X[i]-Y[i])]%mod,
			sum+=abs(X[i]-Y[i]);
		ans1=ans1*C.fac[sum]%mod;
		
		cout<<ans1*ans2%mod<<endl;
	}
	return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注