This week's question seems to be relatively simple
catalogue
A. Combinatorial number problem
A. Combinatorial number problem
Main idea of the title:
Topic idea:
emmm.
Non - number theory contestants can also solve their number theory problems
Considering the multiple problem, we can directly decompose the prime factor
After the prime factor decomposition, the division of the combinatorial number will be changed to the subtraction of the power, so a prefix sum can be obtained for the power
Just judge whether it is greater than all powers of k
However, this place will be blocked by T, because every time you have to calculate n*m and ask t times
So you might as well type the external watch directly and get it directly from O1
Just use the two-dimensional prefix and handle it
Code:
/*** keep hungry and calm CoolGuang!***/
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define d(x) printf("%lld\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e17;
const ll maxn = 1e6+700;
const int mod= 1e9+7;
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
int cnt = 0;
int dp[2005][21];
ll res[2005][2005];
int prime[300];
int pre[30];
int judge(int x){
if(x == 1) return 0;
for(int k=2;k*k<=x;k++)
if(x%k == 0) return 0;
return 1;
}
int check(int i,int k){
if(i<k) return 0;
for(int j=1;j<=cnt;j++)
if(dp[i][j]-dp[k][j]-dp[i-k][j] < pre[j]) return 0;
return 1;
}
int main(){
for(int i=1;i<=21;i++)
if(judge(i))
prime[++cnt] = i;
int T;read(T);read(p);
for(int i=1;i<=cnt;i++){
while(p%prime[i] == 0){
p/=prime[i];
pre[i]++;
}
}
for(int i=1;i<=2000;i++){
ll temp = i;
for(int k=1;k<=cnt;k++) dp[i][k] = dp[i-1][k];
for(int k=1;k<=cnt;k++){
while(temp%prime[k] == 0){
dp[i][k]++;
temp /= prime[k];
}
}
}
for(int i=1;i<=2001;i++){
for(int k=1;k<=2001;k++){
res[i][k] = res[i-1][k] + res[i][k-1] - res[i-1][k-1] + check(i-1,k-1);
}
}
while(T--){
read(n);read(m);
m = min(m,n);
n++;m++;
printf("%lld\n",res[n][m]);
}
return 0;
}C. Relay
Main idea of the title:
Topic idea:
Very simple simulation problem
Just maintain the earliest end time of each player, that is, maintain a small top pile with a priority queue and give priority to the end time of running
So you just need to get the smallest one out of the team every time, and then use this person to update the person "connected" with this person
Add a mark during the period, under which you can check whether you have visited
Code:
/*** keep hungry and calm CoolGuang!***/
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define d(x) printf("%lld\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e17;
const ll maxn = 1e6+700;
const int mod= 1e9+7;
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
vector<int>v[maxn];
ll dis[maxn];
ll a[maxn];
int vis[maxn];
ll bfs(){
ll ans = 0;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
q.push({a[1],1});
vis[1] = 1;
while(!q.empty()){
auto u = q.top();q.pop();
ll w = u.first,id = u.second;
ans = max(ans,w);
for(int e:v[id]){
if(!vis[e]){
q.push({w+a[e],e});
vis[e] = 1;
}
}
}return ans;
}
int main(){
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
read(n);
for(int i=1;i<=n;i++){
read(a[i]);
int x;read(x);
for(int k=1;k<=x;k++){
int y;read(y);
v[i].push_back(y);
}
}
printf("%lld\n",bfs());
return 0;
}D. Words
Main idea of the title:
Topic idea:
For any two strings, the relationship between letters can be judged by n^3
Next, we only need to consider the unique solution, no solution and multiple solutions in the graph
1. Unique solution: the topology path is unique
2. No solution: Ring generation
3. Multiple solutions: the topological path is not unique
Two approaches are recommended:
Topological sorting: when dealing with multi solution problems, topological sorting only needs to consider whether the points with out degree of 0 and in degree of 0 are unique
No solution - there is a ring. There is no need to say more about the solution of this topological sorting
Floyd:
mp[x][y] edge construction means Y > X
Floyd can judge whether there is a self ring. Just judge whether mp[i][i] is 1
In the case of multiple solutions, you can look at the current ranking. Everyone's ranking calculation: just find out how many mp[x][k] are. K satisfies that mp[x][k] is 1, so the ranking of X is n-k
As long as there is no repetition
Only Floyd's code is below
Code:
/*** keep hungry and calm CoolGuang!***/
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define d(x) printf("%lld\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e17;
const ll maxn = 1e6+700;
const int mod= 1e9+7;
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
char s[100][102];
int pre[maxn];
int rk[30],vis[30];
int mp[30][30];
int cnt = 0;
int Find(int x){
return pre[x] == x?x:pre[x] = Find(pre[x]);
}
int main(){
read(n);
for(int i=1;i<=n;i++){
scanf("%s",s[i]+1);
for(int k=1;s[i][k];k++){
vis[s[i][k]-'a'] ++;
}
}
for(int i=0;i<26;i++){
pre[i] = i;
if(vis[i]) cnt++;
}
int cot = cnt;
for(int i=1;i<=n;i++){
for(int k=i+1;k<=n;k++){
int len = strlen(s[i]+1);
for(int j=1;j<=len;j++){
if(s[i][j] != s[k][j]){
int x = s[i][j] - 'a';
int y = s[k][j] - 'a';
int dx = Find(x),dy = Find(y);
if(dx != dy) pre[dx] = dy,cnt--;
mp[x][y] = 1; ///y > x
break;
}
}
}
}
if(cnt > 1) printf("?");
else{
for(int k=0;k<26;k++){
for(int i=0;i<26;i++){
for(int j=0;j<26;j++){
if(mp[i][k] && mp[k][j]) mp[i][j] = 1;
}
}
}
for(int k=0;k<26;k++){
if(mp[k][k]){
printf("!\n");
return 0;
}
}
for(int k=0;k<26;k++){
if(vis[k]){
int res = 0;
for(int j=0;j<26;j++)
if(mp[k][j]) res++;
if(!rk[cot-res]) rk[cot-res] = k+1;
else{
printf("?\n");
return 0;
}
}
}
for(int i=1;i<=cot;i++)
printf("%c",rk[i]-1+'a');
printf("\n");
}
return 0;
}E. elections
Main idea of the title:
Topic idea:
Simulate according to the meaning of the topic
Code:
/*** keep hungry and calm CoolGuang!***/
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define d(x) printf("%lld\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e17;
const ll maxn = 1e6+700;
const int mod= 1e9+7;
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
struct node{
string name;
int id;
ll x;
bool friend operator<(node a,node b){
return a.name < b.name;
}
}q[maxn];
pair<int,int>s[maxn];
int res[maxn];
int main(){
read(m);read(n);
for(int i=1;i<=n;i++){
cin>>q[i].name;
cin>>q[i].x;
q[i].id = i;
}
int cnt = 0;
for(int i=1;i<=n;i++){
if(q[i].x*100>=5*m){
for(int k=1;k<=14;k++)
s[++cnt] = {q[i].x/k,i};
}
}
sort(s+1,s+1+cnt,greater<pair<int,int>>());
for(int i=1;i<=14;i++)
res[s[i].second] ++;
sort(q+1,q+1+n);
for(int i=1;i<=n;i++){
int id = q[i].id;
if(res[id]){
cout<<q[i].name<<" "<<res[id]<<endl;
}
}
return 0;
}