当前位置：网站首页>2022 Nioke Multi-School League Game 4 Solution

2022 Nioke Multi-School League Game 4 Solution

2022-07-31 03:01:00 【Frank_Star】

签到题

N题 Particle Arts / particle art

题目大意
$n$ 个粒子,Each particle has an energy $𝑎_𝑖$ .Pairs collide randomly,The energy of the two particles per collision becomes $𝑎\&𝑏, 𝑎|𝑏$ .
Find the variance of all particle energies after they have stabilized. $𝑛≤10^5,0≤𝑎_𝑖<2^{15}$

考察内容
贪心

分析
after each collision $𝑎\&𝑏, 𝑎|𝑏$ compared to the original,Small is smaller and larger is bigger,So the variance increases monotonically after each collision.
Preprocess the number of bits per bin,Put them in as few numbers as possible,The result obtained is the final result,At this point the variance is the largest.

Open when seeking variance__int128就行.

#include<bits/stdc++.h>
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
using namespace std;
const int N=1e6+10;
ll n,m,a[N];
ll b[N];
ll num[17];

__int128 gcd(__int128 a,__int128 b){
    
    if(b==0)
        return a;
    else
        return gcd(b,a%b);
}

void print(__int128 x){
      
    if(!x){
      
        cout<<"0";
    }  
    string ret="";  
    while(x){
      
        ret+=x%10+'0';  
        x/=10;  
    }  
    reverse(ret.begin(),ret.end());  
    cout<<ret;  
} 

int main(){
     
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

	cin>>n;
	for(int i=1;i<=n;i++){
    
		cin>>a[i]; 
		int p=0;
		while(a[i]>0){
    
			num[p]+=a[i]%2;
			a[i]/=2;
			p++;
		}
	}
	
	for(int i=1;i<=n;i++){
    
		for(int j=0;j<=15;j++){
    
			if(num[j]>0){
    
				num[j]--;
				b[i] += (1<<j);
			}
		}
	}
	
	__int128 sum=0;
	for(int i=1;i<=n;i++){
    
		sum+=b[i];
	}
	
	__int128 d1=0,d2=n*n*n;
	for(int i=1;i<=n;i++){
    
		__int128 t1=b[i]*n-sum;
		d1+=t1*t1;
	}
	
	__int128 g1=gcd(d1,d2);
	d1/=g1; d2/=g1;
	
	if(d1==0){
    
		d2=1;
	}
    
	print(d1);
    cout<<"/";
    print(d2);
    
	return 0;
}

基本题

K题 NIO’s Sword / NIO的剑

题目大意
玩家初始有一把攻击力为 $0$ 的剑,需要依次击杀 $(1\le n\le 10^{6})$ 个敌人,仅当攻击力模 $n$ 与 $i$ 同余才能击杀第 $i$ 个敌人.
玩家可以升级剑,每次升级相当于在当前攻击力后面添加一个数字,问最少需要几次升级.

考察内容
贪心,暴力

分析
$1\le n\le 10^{6}$ ,So upgrade at most7次（在后面加7个数字）Can definitely kill an enemy.for every enemy,You can directly enumerate the number of upgrades.

#include<bits/stdc++.h>
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
using namespace std;
const int N=1e6+10;
ll n,m,a[N];
ll po[10];

int main(){
     
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	po[0]=1;
	for(int i=1;i<=7;i++){
    
		po[i]=po[i-1]*10; // 预处理10的幂次 
	}

	cin>>n;
	
	ll ans=0; 
	ll cnt=0; // The value of the current weapon 
	
	for(int i=1;i<=n;i++){
     // Enumerate each monster 
		if(cnt%n==i%n)continue; // Can be defeated without leveling up 
		
		for(int j=1;j<=7;j++){
     // 最多升级7You can definitely find a way to defeat the monsters 
			cnt*=10;
			cnt%=n;
			
			if(po[j]>=n){
    
				cnt=i%n; 
				ans+=j;
				break;
			}
			
			// po[j]<n
			if(cnt<=i%n && cnt+po[j]-1>=i%n){
     // 可以击败 
				cnt=i%n; 
				ans+=j;
				break;
			} 
			else if(cnt<=i%n+n && cnt+po[j]-1>=i%n+n){
     // 可以击败 
				cnt=i%n; 
				ans+=j;
				break;
			} 
		}	
	}
	
	cout<<ans<<endl;
	
	return 0;
}
/* 输入： 1000000 输出： 5877904 */

D题 Jobs (Easy Version) / 工作（简单版）

题目大意
有 $n$ 个公司,第 $i$ companies have $𝑚_𝑖$ 个工作,Each job has numerical requirements for each of the three competencies,All three competencies must be met to be qualified for the job.A person can work for a company as long as he is competent for any job in the company.
询问 $q$ 次,For each question, a random number of three abilities is given to a person,Find out how many companies this person can work for.
强制在线.
$𝑛≤10,∑𝑚_𝑖≤10^6 , 𝑞≤2×10^6$ ,The numerical value of ability does not exceed400

考察内容
贪心,排序,暴力,复杂度优化

分析
解法不唯一.

All work for each unit is first based on the sum of the three abilitiessum从小到大排序,然后暴力判断即可.

A person's three abilities are not enoughsum时,The latter work will certainly not be up to the task,可以直接break掉.
Read and optimize.

#include<bits/stdc++.h>
#include<random>
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
#define int long long
using namespace std;
const int N=1e5+5;
const int maxq=2e6+5;
const ll mod=998244353;
ll read(ll &n){
    
	char ch=' '; ll q=0,w=1;
	for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
	if(ch=='-')w=-1,ch=getchar();
	for(;ch>='0'&&ch<='9';ch=getchar())q=q*10+ch-48;
	n=q*w; return n;
}

ll n,q,seed; 
ll m[N];
ll po[maxq];

struct node{
    
	ll q1,q2,q3;
	ll sumq; // q1+q2+q3
}a[11][N];

ll solve(ll IQ,ll EQ,ll AQ){
     // Calculate how many companies you can get hired by 
	ll sum0=IQ+EQ+AQ; // The sum of the three quotients 
	ll num=0;
	
	for(int i=1;i<=n;i++){
     // Judge whether it can be the firsticompany hired 
		int F=0;
		
		// 枚举m[i]份工作 
		for(int j=1;j<=m[i];j++){
    
			if(sum0<a[i][j].sumq){
     // The sum of three quotients is not enough,这家公司不行 
				break;
			}
			
			// sum0>=a[i][j].sumq时 
			if(IQ>=a[i][j].q1 && EQ>=a[i][j].q2 && AQ>=a[i][j].q3){
    
				F=1; // 可以胜任 
				break;
			}
		}
		if(F)num++;
	}
	return num;
}


bool cmp(node x,node y){
    
	return x.sumq<y.sumq; // "三个和"Smaller jobs come forward 
}

signed main(){
     // wa..
	read(n); read(q);
	for(int i=1;i<=n;i++){
    
		read(m[i]);
		for(int j=1;j<=m[i];j++){
    
			read(a[i][j].q1); read(a[i][j].q2); read(a[i][j].q3);
			a[i][j].sumq=a[i][j].q1+a[i][j].q2+a[i][j].q3;
		}	
		sort(a[i]+1,a[i]+m[i]+1,cmp); // 排序 
	}
	read(seed); // Read in a random seedseed 
	std::mt19937 rng(seed);
	std::uniform_int_distribution<> u(1,400);
	
	ll seedmod=seed%mod; // 防止爆long long 
	po[0]=1;
	for(int i=1;i<=q;i++){
    
		po[i]=po[i-1]*seedmod%mod; // 预处理seed的幂次 
	}
	
	ll ans=0;
	
	int lastans=0;
	for (int i=1;i<=q;i++){
     // 询问q次 
	    int IQ=(u(rng)^lastans)%400+1;  // The IQ of the i-th friend
	    int EQ=(u(rng)^lastans)%400+1;  // The EQ of the i-th friend
	    int AQ=(u(rng)^lastans)%400+1;  // The AQ of the i-th friend
	    lastans=solve(IQ,EQ,AQ)%mod;  // The answer to the i-th friend
		
		ans+=lastans*po[q-i]%mod;
		ans%=mod;
	}
	
	cout<<(ans+mod)%mod<<endl;

	return 0;
}
/* 3 5 3 2 1 2 400 400 400 1 1 2 3 1 3 2 2 3 1 2 3 3 2 2 3 1 3 2 1 998244353 */

H题 Wall Builder II / Wall BuilderII

题目大意
给 $\leq 100)$ 个 $1 * 1$ 的矩形, $n - 1$ 个 $1 * 2$ 的矩形, $n - 2$ 个 $1 * 3$ 的矩形…, $1$ 个 $1 * n$ 的矩形,把这些矩形拼成一个大矩形,求大矩形的最小周长.

考察内容
贪心,构造

分析
$n$ 已经给定了,So the total area can be directly enumerated and calculated.
容易发现,gave so much $1 * n$ of small pieces,Arrange this total area into an arbitrary one $x * y$ 的大矩形,They can all be made out of small pieces.A factor that directly enumerates the total area,Just pick the one that is closest to the square.

Be greedy when you swing,Layer upon layer,Each layer first uses the remaining small pieces,The longest one can fit.

#include<bits/stdc++.h>
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
using namespace std;
const int N=105;
ll n;
ll num[N]; // num[i]记录1*ithe number of blocks 

int p=0;
struct node{
    
	ll x1,y1,x2,y2;	
}a[N*N];

int main(){
     
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t; cin>>t;
	while(t--){
    
		p=0; // 初始化p 
		
		cin>>n; // 最小周长
		ll sum=0; // 总面积, sum<=171700
		for(int i=1;i<=n;i++){
    
			sum+=i*(n+1-i);	
		}
		for(int i=1;i<=n;i++){
    
			num[i]=n+1-i;
		}
		
		ll len1=(n+1)*2; // Record the minimum circumference 
		
		ll h=sqrt(sum);
		for(int i=h;i>=1;i--){
     // 枚举sum的因数 
			if(sum%i==0){
     // 可以整除 
				ll xall=sum/i;
				ll yall=i;
				
				for(int i=1;i<=yall;i++){
    
					int j=0;
					while(j<xall && p<=n*(n+1)/2){
    
						for(int k=min(n,xall-j);k>=1;k--){
     // 贪心,Use as long blocks as possible 
							if(num[k]==0)continue;
							
							// num[k]>0时 
							num[k]--;
							
							a[++p].x1=j;
							a[p].y1=i-1; 
							a[p].x2=j+k;
							a[p].y2=i;
							
							j+=k;
							break; 
						}
					}
					// j>=xall时, Then look at the previous line 
				}
				
				len1=(i+sum/i)*2; // 更新len1
				break;
			}
		}
		
		cout<<len1<<endl;
		for(int i=1;i<=p;i++){
    
			cout<<a[i].x1<<' '<<a[i].y1<<' '<<a[i].x2<<' '<<a[i].y2<<endl;
		} 
	}
	return 0;
}
/* 1 4 */

进阶题

A题 Task Computing / 任务计算

题目大意
从 $n$ selected tasks $m$ 个 $𝑎_1,𝑎_2,......,𝑎_𝑚)$ come out and sort them arbitrarily,收益是 $_{𝑖=1}^𝑚 {𝑤_{𝑎_𝑖 }}∏_𝑗^{𝑖−1}{𝑝_{𝑎_𝑗}}$ ,求最大收益.

$1\le n\le 10^5, 1\le m \le \min(n,20)$

考察内容
动态规划,排序

分析
First for the entire array,用类似 “国王游戏” The methods used in it are sorted again.

Then go to dynamic programming.
状态：
$f [i]$ Indicates selected $i$ maximum benefit for each task.

边界：
$f [0] = 0$ ,There is no benefit when you do not choose.

转移：
$f [j] * a [i] . p + a [i] . w > f [j + 1]$ 时, $f [j + 1] = f [j] * a [i] . p + a [i] . w$
Transfer backwards,Cancellation of aftereffects.

#include<bits/stdc++.h>
#define ll long long
#define cer(x) cerr<<(#x)<<" = "<<(x)<<'\n'
#define endl '\n'
using namespace std;
const int N=1e5+10;
ll n,m;
struct node{
    
	ll w,q;
}a[N];

bool cmp2(node x,node y){
     // 类似"国王游戏"中的排序 
	return x.w*(10000-y.q)>y.w*(10000-x.q); // 
} 

double f[25];

int main(){
     // "国王游戏" + dp
	cin>>n>>m; // 选m个,m<=20 
	for(int i=1;i<=n;i++){
    
		cin>>a[i].w;	
	}
	for(int i=1;i<=n;i++){
    
		cin>>a[i].q;	
	}
	sort(a+1,a+n+1,cmp2); // 排序 

	f[0]=0;
	for(int i=1;i<=m;i++){
    
		f[i]=-1e9-10;
	}
	
	for(int i=n;i>0;i--){
    
		for(int j=m-1;j>=0;j--){
    
			f[j+1]=max(f[j+1], f[j]*a[i].q/10000+a[i].w);
		}
	}	
	printf("%.7f\n",f[m]);
	return 0;
}
/* 输入： 3 2 1000000000 1000000000 999999999 8000 8000 12000 输出： 2199999999 */