18级个人训练赛--2

A – Engines AtCoder 4900
题意：

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const ll maxn = 1e6+10;
const ll inf = 1e14;
struct node{
	ll x,y;
	 
}r[1100];;
bool cmp(node a,node b){
	return atan2(a.x,a.y) < atan2(b.x,b.y);
}
int main(){
	ll n,x,y;
	cin >> n;
	for(ll i = 0; i < n; i++){
		cin >> r[i].x >> r[i].y;
	}
	ll ans = 0;
	sort(r,r+n,cmp);
	for(ll i = 0; i < n; i++){
		x = r[i].x ; y = r[i].y;
		ans = max(ans,x*x+y*y);
		for(ll j = (i+1)%n; j != i; j = (j+1)%n){
			x += r[j].x ; y += r[j].y;
			ans = max(ans,x*x+y*y);
		}
		
	}
	
	double ans1 = sqrt(ans);
	printf("%.13lf\n",ans1);
	return 0;
}

B --Consecutive Integers AtCoder 5037
思路：水题，签到~

#include<bits/stdc++.h>

using namespace std;
int main(){
	long long n,m;
	cin>>n>>m;
	cout<<n-m+1<<endl;
	return 0;
}

C-- ModSum -AtCoder 4873
思路：水题，本没思路，看看样例猜了个规律，就A了…

#include<bits/stdc++.h>

using namespace std;
int main(){
	long long int n;
	cin>>n;
	long long int sum = 0 ;
	for(long long int i=1;i<=n-1;i++)
	  sum+=i;
	cout<<sum<<endl;
	
	return 0;
}

D - Shortest Path on a Line AtCoder 5635

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const ll maxn = 1e6+10;
const ll inf = 1e14;

vector<pii> ve[maxn];
ll dis[maxn];
priority_queue<pii,vector<pii>,greater<pii>> heap;
int N,M;

void init(){
	for(int i = 1;i<=N;i++) dis[i] = inf;
	for(int i = 1;i<=N;i++) ve[i].push_back({0,i-1});
	
}

ll Dji(){
	heap.push({0,1});
	dis[1] = 0;
	
	while(heap.size()){
		auto cur = heap.top();heap.pop();
		ll d = cur.first,id = cur.second;
		for(auto v:ve[id]){
			ll w = v.first,id2 = v.second;
			if(d+w<dis[id2]){
				dis[id2] = d+w;
				heap.push({dis[id2],id2});
			}
		}
	}
	if(dis[N] == inf) return -1;
	return dis[N];
}

int main(){
	cin>>N>>M;
	init();
	int a,b,c;
	for(int i = 0;i<M;i++){
		scanf("%d%d%d",&a,&b,&c);
		ve[a].push_back({c,b});
	}
	cout<<Dji()<<endl;
	return 0;
}

E–Counting of Trees AtCoder 5633

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1E5+7;
ll arr[N];
const int MOD=998244353;
ll ksm(ll x, ll y){
	ll res=1;
	while(y){
		if(y&1) res=res*x%MOD;
		x=x*x%MOD;
		y>>=1;
	}
	return res%MOD;
}

int main(){
	ll n;
	cin>>n;
	ll sum=1;
	ll x;
	ll s=0;
	for(int i=1;i<=n;i++){
		cin>>x;
		if(i==1&&x!=0) sum=0;
		arr[x]++;
		s=max(s,x);
	}
	for(int i=s;i>=0;i--){
		if(arr[i]==0) sum=0;
		if(i>1)	sum=sum*ksm(arr[i-1],arr[i])%MOD;
	}
	if(arr[0]>1) sum=0;
	printf("%lld\n",sum);
	
	return 0;
}

F -Monsters Battle RoyaleAtCoder 4297

思路：读懂题以后，其实就是求所有数的最大公因数。

#include<bits/stdc++.h>

using namespace std;
/*int gcd(int a,int b){ return b?(b,a%b):a; }*/
int main(){
	long long int a,n,x;
	cin>>n;
	cin>>a;
	n--;
	while(n--){
		
		cin>>x;
		a = __gcd(a,x);	
	}
	cout<<a<<endl;
	return 0;
}

G - Powerful Discount Tickets AtCoder 4864
思路:看完题后就是有票能打半折，那么肯定是要每次更新最大的数去打折，这样得到的折扣才最大，那么要用到优先队列（从大到小排列）代码如下很好理解

#include<bits/stdc++.h>

#define ll long long 

using namespace std;
int main(){
	int n,m;
	priority_queue<int>q;
	cin>>n>>m;
	ll w;
	while(n--){
		cin>>w;
		q.push(w);
	}
	ll ans = 0;
	while(m){
		w = q.top()/2;
		q.pop();
		q.push(w);
		m--;
	}
	while(!q.empty()){
		ans += q.top();
		q.pop();
	}
	cout<<ans<<endl;
	return 0;
}

H - Attack Survival AtCoder 4870

思路：这个其实也很好理解，读懂题就能AC了应该。就是你得分了，你的分数不会增加，你的所有队友的分数将会减少，那么我们对所有问题的得分选手进行标记，然后在所有对手的循环里面我们将除了自己答题以外的都减去，然后进行判断输出就行了！

#include<bits/stdc++.h>
#define maxn 100005
using namespace std;

int a[maxn],b[maxn];

int main(){
	int n,k,q;
	cin>>n>>k>>q;
	
	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));
	
	for(int i=1;i<=q;i++){
		int flag;
		cin>>flag;
		b[flag]++;
	}
	
	for(int i=1;i<=n;i++){
	
		a[i] = k-(q-b[i]);
		
		if(a[i]<=0)
		 cout<<"No"<<endl;
		else
		  cout<<"Yes"<<endl;
	}
	return 0;
}

I - Lower AtCoder 4871

思路：主要是模拟这个过程吧，一开始我用了两个for循环来做，优化了不少次，却总是超时，然后我就思考能否一个for来解决，其实也是可以了。就AC了

#include<bits/stdc++.h>
#define maxn 100000009
using namespace std;

int a[maxn];
int main()
{
	int t;
	while(cin>>t)
	{
		int con=0,num=0;
		for(int i=1;i<=t;++i)
		{
			cin>>a[i];
		}
		int k = a[1];
		for(int i =2;i<=t;++i)
		{
			if(k>=a[i])
			{
				num++;
				k=a[i];
			}
			if(k<a[i])
			{
				con = max(num,con);
				num = 0;
				k = a[i];
			}
		}
		con = max(con,num);
		cout<<con<<endl;
	}
}

J - Kleene Inversion –AtCoder 5165

思路：这个题能找找规律，具体什么记得不太清楚了，就是找规律然后快速乘，不然数字太大会超时。不是很难，推道的过程比较难吧。

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

LL a[10005];

LL M = 1e9 + 7;

LL pow(LL a,LL b,LL M)
{ 
   LL c = a * b - (LL)(a*b/M + 0.5)*M; 
   return c < 0 ? c + M : c;
}

int main()
{
   LL n,m;
   cin>>n>>m;
   for(int i = 1; i<=n; ++i)
     cin>>a[i];
     
     LL num1= 0,num2 =0;
     
    for(int i = 1; i<n; ++i){
      for(int j = i+1; j<=n; ++j){
       if(a[i]>a[j])
        num1 ++;
      }
    } 
    
    sort(a+1,a+n+1,greater<LL>());
    for(int i = 1; i<n; ++i){
      for(int j = i+1; j<=n; ++j){
          if(a[i]>a[j])
            num2++;
         }
      }
      
    LL flag1 = m,flag2 = m;
    
      if(flag1 % 2==0){
      	flag1 = m/2;
		flag2 = m-1;
	  }
	  
      else{
      	flag1 = m;
	    flag2  = (m-1)/2;
	  }
	   
      cout<<(pow(num1,m,M)%M + pow(flag1,flag2,M)*num2 )%M<<endl;
}

M - AB Substrings AtCoder 5039

思路：这个，暴力吧，读懂题后就暴力，暴力学的美学多好啊。其实是我笨(～￣(OO)￣)ブ

#include<bits/stdc++.h>
#define ll long long 

#define maxn 10005
using namespace std;
ll a[maxn][3]={0};
string s[maxn];
string st="";
int main(){
	ll n;
	cin>>n;
	
	for(ll i =0;i<n;i++){
	cin>>s[i];
	if(s[i][0] == 'B')
	   a[i][0]++;
	if(s[i][s[i].size()-1]=='A')
	   a[i][1]++;
	   }
	   
	ll flag = 0;
	
	for(ll i=0;i<n;i++){
		if(a[i][0] == 0&&a[i][1]!=0){
			flag = 1;
			st+=s[i];
			a[i][2] = -1;
			break;
		}
	}
	
	ll q = 0;
	//1
	if(flag == 1){
		for(ll i=0;i<n;i++){
			if(a[i][2] == -1){
				continue;
			}
			else{
				if(a[i][0]!=0&&a[i][1]!=0){
					st+=s[i];
					a[i][2] = -1;
				}
			}
		}
		for(ll i=0;i<n;i++){
			if(a[i][2]==-1){
				continue;
			}
			else{
			if(a[i][0]!=0){
				st+=s[i];
				a[i][2]=-1;
				break;
			}	
			}
		}
		for(ll i=0;i<n;i++){
			if(a[i][2]==-1){
				continue;
			}
			else{
				if(q%2==0){
					if(a[i][1]!=0){
						st+=s[i];
						a[i][2] =-1;
						i=-1;
						q++;
					}
				}
				else{
					if(a[i][0]!=0){
						st+=s[i];
						a[i][2]=-1;
						i=-1;
						q++;
					}
				}
			}
		}
		for(ll i=0;i<n;i++){
			if(a[i][2]!=-1){
				st+=s[i];
				a[i][2]=-1;
			}
		}
	}
	
	
	//2
	if(flag ==0){
		for(ll i=0;i<n;i++){
			if(a[i][1]!=0&&a[i][2]!=-1){
				st+=s[i];
				a[i][2] =-1;
				break;
			}
		}
		for(ll i=0;i<n;i++){
			if(a[i][2]==-1){
				continue;
			}
			else{
				if(a[i][0]!=0&&a[i][1]!=0){
					st+=s[i];
					a[i][2]=-1;
				}
			}
		}
		for(ll i=0;i<n;i++){
			if(a[i][2]==-1){
				continue;
			}
			else{
				if(a[i][0]!=0){
					st+=s[i];
					a[i][2]=-1;
				}
			}
		}
		for(ll i=0;i<n;i++){
			if(a[i][2]!=-1){
				st+=s[i];
				a[i][2]=-1;
			}
		}
	}
	
	
	
	ll num =0;
	for(ll i=0;i<st.size()-1;i++){
		if(st[i]=='A'&&st[i+1]=='B'){
			num++;
		}
	}
	cout<<num<<endl;
	return 0;
}