"Shanda Diwei Cup" the 12th Shandong ICPC undergraduate program design competition

Make up the question by comparing the dishes of the star team

A - Seventeen（ structure , Sign in ）

use 1~n For all numbers +,-,*,(,), Make up the formula so that the number is 17.

Ideas ： Find the rules , Less than 4 It is absolutely impossible to form 17, When n by 4 when , Can make (4+1)*3+2 obtain 17,n by 5 when , Can make 4*5-3*(2-1), about n For even when , We can use 4 Based on , The rest of the adjacent numbers are formed in pairs (i+1-i) In the form of 1, So it has no effect on the answer ;n In an odd number of , with 5 Based on , Just do the same .

AC Code：

#include <bits/stdc++.h>

typedef long long ll;
const int N=2e5+5;
int n;

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cin>>n;
	if(n<4){
		std::cout<<-1<<'\n';
		return 0;
	}
	if(n%2==0){
		std::cout<<"(4+1)*3+2";
		for(int i=5;i<=n;i+=2){
			std::cout<<"*("<<i+1<<"-"<<i<<")";
		}
		std::cout<<'\n';
	}
	else{
		std::cout<<"4*5-3*(2-1)";
		for(int i=6;i<=n;i+=2){
			std::cout<<"*("<<i+1<<"-"<<i<<")";
		}
		std::cout<<'\n';
	}
	return 0;
}

os： This type of question is similar to the one given by elder martial brother , But I didn't think of it in time , I didn't think of it for a long time 4 Is the minimum limit , bring WA A lot of hair ,, It's ridiculous

K - Coins（ law , Violence enumeration ）

A Yes 4 Grow coins 2,3,17,19,B Yes 4 Grow coins 5,7,11,13, There are several groups asking x, Ask who can make it up with fewer coins x.

Ideas ： If there is a and b Coins of two denominations , And a<b, Then every a individual b Coins can be used b individual a Coins replace , so a Coin is less than b, So for a relatively small range, we can get the answer through violent enumeration , In the case of a large number, the answer is certain .

AC Code：

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f
typedef long long ll;
const int N=1e5+5;
int A[]={0,2,3,17,19};
int B[]={0,5,7,11,13};
int a[N],b[N];
int x,q;

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	memset(a,INF,sizeof(a));
	memset(b,INF,sizeof(b));
	a[0]=0,b[0]=0;
	for(int i=1;i<=4;i++){
		for(int j=A[i];j<=100000;j++){
			a[j]=std::min(a[j],a[j-A[i]]+1);
		}
	}
	for(int i=1;i<=4;i++){
		for(int j=B[i];j<=100000;j++){
			b[j]=std::min(b[j],b[j-B[i]]+1);
		}
	}
	std::cin>>q;
	while(q--){
		std::cin>>x;
		if(x>=100000){
			std::cout<<"A"<<'\n';
			continue;
		}
		if(a[x]>=INF&&b[x]>=INF){
			std::cout<<-1<<'\n';
		}
		else if(a[x]==b[x]){
			std::cout<<"both"<<'\n';
		}
		else if(a[x]>b[x]){
			std::cout<<"B"<<'\n';
		}
		else if(a[x]<b[x]){
			std::cout<<"A"<<'\n';
		}
	}
	return 0;
}

os： This problem was worked out for a long time and finally came out , As a result, I got stuck during the retest , Send

H - Counting（ Barrel maintenance ）

give k The initial coordinates of the individual , give k Individuals in T Within seconds , Calculate the number of people who overlap every second .

Ideas ： Direct simulation , Modify the current status and the next status after each walk , Notice that the logarithm of people is C(n,2).

AC Code：

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f
typedef long long ll;
const int N=3e3+5;
const int M=2e3+5;
int n,m,T,k;
int ans[N],x[M],y[M],mp[M][M];
char s[M][N];

int main(){
	scanf("%d%d%d%d",&n,&m,&k,&T);
	for(int i=0;i<k;i++){
		scanf("%d%d",&x[i],&y[i]);
		ans[0]-=(mp[x[i]][y[i]]-1)*mp[x[i]][y[i]]/2;
		mp[x[i]][y[i]]++;
		ans[0]+=(mp[x[i]][y[i]]-1)*mp[x[i]][y[i]]/2;
	}
	for(int i=0;i<k;i++){
		scanf("%s",s[i]);
	}
	int cnt=1;
	for(int j=0;j<T;j++){
		ans[cnt]=ans[cnt-1];
		for(int i=0;i<k;i++){
			ans[cnt]-=(mp[x[i]][y[i]]-1)*mp[x[i]][y[i]]/2;
			mp[x[i]][y[i]]--;
			ans[cnt]+=(mp[x[i]][y[i]]-1)*mp[x[i]][y[i]]/2;
			if(s[i][j]=='U') x[i]--;
			else if(s[i][j]=='D') x[i]++;
			else if(s[i][j]=='R') y[i]++;
			else if(s[i][j]=='L') y[i]--;
			ans[cnt]-=(mp[x[i]][y[i]]-1)*mp[x[i]][y[i]]/2;
			mp[x[i]][y[i]]++;
			ans[cnt]+=(mp[x[i]][y[i]]-1)*mp[x[i]][y[i]]/2;
		}
		++cnt;
	}
	for(int i=0;i<=T;i++){
		printf("%d\n",ans[i]);
	}
	return 0;
}

os： When I was doing the problem, my teammates opened the computational geometry , I didn't even look at this question ,,, Sign in completely, sobbing

E - Subsegments（ thinking , bucket ）

  Given array a And a number x, Ask how many intervals the product of the module gets the number x.

Ideas ： There are two scenarios ：x==0 when , Calculation contains 0 That's enough , Note that it's not just in the array that 0, Mold that thing is equal to 0 Also calculate ;x It's not equal to 0 when , The same to 0 Demarcation , Maintain prefix product for each segment , use map Maintain the barrel .

AC Code：

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f
typedef long long ll;
const int N=5e5+5;
const int mod=998244353;
ll n,x,b,res,ans;
ll a[N];

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin>>n>>x;
	if(x==0){
		for(int i=1;i<=n;i++){
			std::cin>>b;
			a[i]=b%mod;
			if(a[i]==0) res=i;
			ans+=res;
		}
	}
	else{
		std::map<int,int>mp;
		res=mp[x]=1;
		for(int i=1;i<=n;i++){
			std::cin>>b;
			a[i]=b%mod;
			if(a[i]==0){
				mp.clear();
				res=mp[x]=1;
			}
			else{
				res=res*a[i]%mod;
				ans+=mp[res];
				++mp[res*x%mod];
			}
		}
	}
	std::cout<<ans<<'\n';
	return 0;
}

os： Learn the code of the elder martial brother team , I still need to strengthen some processing

J - Football Match（ Computational geometry ）

  Give the proportion of a flag , give A,B The coordinates of two points , Find the coordinates of all other points of the flag .

 os： This question is really speechless , Paper questions are different from those on Niuke ,, The paper does not say that the flag can rotate ,, It took us so long in vain ,, Well, it's because we overestimated our strength that we started the problem of computational geometry , Send

Ideas ： Calculate the length of the line segment according to the scale , You can get the coordinates of the points . For this question , We can use the data given in the original question to scale and rotate . It's not hard to think , But it's very troublesome .

notes ： For rotation about a point , Matrix rotation can be used to directly bring in ：

Matrix right multiplication （x,y） The transpose matrix of . actually , We can find out , Do not consider clockwise or counterclockwise rotation , Direct algebra , According to the positive and negative of the angle . 

AC Code：

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f
typedef long long ll;
typedef long double ld;
const double PI=acos(-1);
int t;
ld xa,ya,xb,yb;
ld xx[]={
	30.000000,30.000000,15.000000,16.347084,20.706339,17.179628,18.526712,15.000000,11.473288,12.820372,9.293661,13.652916
};
ld yy[]={
	20.000000,0.000000,16.000000,11.854102,11.854102,9.291796,5.145898,7.708204,5.145898,9.291796,11.854102,11.854102
};

void init(){
	ld MN=(6*sin(PI*2/5))/(1+sin(PI/10));
	ld PF=MN*sin(PI/10);
	ld OP=6*cos(PI*2/5);
	ld PG=6*sin(PI*2/5);
	ld OF=sqrt(PF*PF+OP*OP);
	//F
	xx[3]=15+PF;
	yy[3]=10+OP;
	//G
	xx[4]=15+PG;
	yy[4]=10+OP;
	//H
	xx[5]=15+OF*cos(PI/10);
	yy[5]=10-OF*sin(PI/10);
	//I
	xx[6]=15+6*sin(PI/5);
	yy[6]=10-6*cos(PI/5);
	//J
	yy[7]=10-OF;
	//K
	xx[8]=15-6*sin(PI/5);
	yy[8]=10-6*cos(PI/5);
	//L
	xx[9]=15-OF*cos(PI/10);
	yy[9]=10-OF*sin(PI/10);
	//M
	xx[10]=15-PG;
	yy[10]=10+OP;
	//N
	xx[11]=15-PF;
	yy[11]=10+OP;
}

int main(){
	init();
	scanf("%d",&t);
	while(t--){
		scanf("%Lf%Lf%Lf%Lf",&xa,&ya,&xb,&yb);
		xb-=xa,yb-=ya;
		ld sinn=xb,coss=yb;
		for(int i=0;i<12;i++){
			ld sinx=xx[i];
			ld cosx=yy[i];
			ld cosp=cosx*coss-sinx*sinn;
			ld sinp=sinx*coss+cosx*sinn;
			ld ansx=sinp/20+xa;
			ld ansy=cosp/20+ya;
			printf("%.10Lf %.10Lf%c",ansx,ansy,i==11?'\n':' ');
		}
	}
	return 0;
}

os： Study of the wygg Team code , Simple and clear ,tqllllll！！！

Let's do that first. , Limited ability , Next year's provincial competition will be fought again ！

If there is any mistake, please advise , thank you ！