AtCoder Beginner Contest 362

时间：2024-07-15 07:00:18

目录

A - Buy a Pen

B - Right Triangle

C - Sum = 0

D - Shortest Path 3 

E - Count Arithmetic Subsequences

F - Perfect Matching on a Tree

G - Count Substring Query

A - Buy a Pen

按照题目要求简单模拟分三中情况取最小值即可

void solve(){
    
    int a,b,c; cin>>a>>b>>c;
    string s; cin>>s;
    if(s[0]=='R') cout << min(b,c) << endl;
    else if(s[0]=='B') cout << min(a,b) << endl;
    else cout << min(a,c) << endl;
    return ;
}

B - Right Triangle

要求是不是直角三角形分三种情况然后用向量的叉积为0即可

int x[4],y[4];

void solve(){
    
	for(int i=1;i<=3;i++) cin>>x[i]>>y[i];
	
	bool ok = false;
	
	auto check = [&](int a,int b,int c){
		int y1 = y[a] - y[b];
		int x1 = x[a] - x[b];
		int y2 = y[c] - y[b];
		int x2 = x[c] - x[b];
		return x1*x2+y1*y2==0;
	};
	if(check(2,1,3) or check(1,2,3) or check(1,3,2)) ok = true;
	cout << (ok ? "Yes" : "No") << endl;    
    return ;
}

C - Sum = 0

首先队友是不是有解我们可以通过答案是不是处于上界和下界即可，其次我们可以先贴着下界，然后往上尽可能加不超过上界的值即可

LL l[N],r[N];
void solve(){
    
    cin>>n;
    LL down = 0,up = 0;
    for(int i=1;i<=n;i++){
    	cin>>l[i]>>r[i];
    	down += l[i];
    	up += r[i];
    }
    if(down<=0 and 0<=up){
    	cout << "Yes" << endl;
    	LL now = down;
    	
    	for(int i=1;i<=n;i++){
    		LL t = min(0ll-now,r[i]-l[i]);
    		cout << t+l[i] << ' '; 
    		now += t;
    	}
    	cout << endl;
    }
    else{
    	cout << "No" << endl;
    }
    return ;
}

D - Shortest Path 3 

简单的最短路加上点权即可，在原来基础上多算一个点权，注意PII 开longlong

vector<PII> g[N];
LL a[N];
LL d[N];
bool st[N];

void solve(){
    
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    
    while(m--){
    	int a,b,c; cin>>a>>b>>c;
    	g[a].push_back({b,c});
    	g[b].push_back({a,c});
    }
    auto dijkstra = [&](){
    	priority_queue<PII,vector<PII>,greater<PII>> q;
    	for(int i=1;i<=n;i++) d[i] = 2e18;
    	d[1] = a[1];
    	q.push({a[1],1});
    	while(!q.empty()){
    		auto [cost,u] = q.top(); q.pop();
    		if(st[u]) continue;
    		st[u] = true;
    		for(auto&[v,w]:g[u]){
    			if(d[v]>cost+w+a[v]){
    				d[v] = cost+w+a[v];
    				q.push({d[v],v});
    			}
    		}
    	}
    };
    dijkstra();
    
    for(int i=2;i<=n;i++) cout << d[i] << ' ';
    cout << endl;
    return ;
}

E - Count Arithmetic Subsequences

注意到很小的数据范围，要求我们求等差数列，等差数列的性质由首项，公差和项数决定，可以得知本题需要使用dp，考虑到要维护项所以需要开一个维度维护，同时我们不知道公差，可以开一个维度离散化维护公差，由题目数据范围可以得到只有n*n个公差，转移来源与上一个点所在的位置和公差

LL dp[M][M][M*M];
LL ans[M];
LL a[N];

void solve(){
    
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    
    vector<LL> v; 
    for(int i=1;i<=n;i++)
    	for(int j=1;j<=i;j++)
    		v.push_back(a[i]-a[j]);
    		
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    
    auto find = [&](LL x){
    	return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
    };
    
    for(int i=1;i<=n;i++){
    	for(int k=1;k<i;k++){ // 前一个点
    		for(int t=1;t<=k;t++){
    			LL j = find(a[i]-a[k]);
    			if(t+1==2){
    				dp[i][t+1][j] += 1;
    			}
    			else{
    				dp[i][t+1][j]+=dp[k][t][j];
    			}
    			dp[i][t+1][j]%=mod;
    		}
    	}
    }
    
    for(int i=1;i<=n;i++)
    	for(int j=1;j<=v.size();j++)
    		for(int k=1;k<=n;k++){
    			ans[k] += dp[i][k][j];
    			ans[k] %= mod;
    		}
    		
    for(int i=1;i<=n;i++){
    	if(i==1) cout << n << ' ';
    	else cout << ans[i] << ' ';
    }
    cout << endl;
    return ;
}

F - Perfect Matching on a Tree

我们要求最大的的距离匹配，可以想到重心的性质然后对于不同的树进行匹配一定是最优的

所以求重心即可

int rt= - 1,rsz;
int sz[N];
vector<int> g[N];
vector<int> G[N];
int idx;

void dfs(int u,int fa){
	sz[u] = 1;
	int res = 0;
	for(auto&v:g[u]){
		if(v==fa) continue;
		dfs(v,u);
		sz[u] += sz[v];		
		res = max(res,sz[v]);
	}
	res = max(res,n-sz[u]);
	if(rt == -1 or res<rsz){
		rt = u;
		rsz = res;
	}
}
void getson(int u,int fa){
	G[idx].push_back(u);
	for(auto&v:g[u]){
		if(v==fa) continue;
		getson(v,u);
	}
}
void solve(){
    
    cin>>n;
    for(int i=1;i<n;i++){
    	int a,b,w; cin>>a>>b;
    	g[a].push_back(b);
    	g[b].push_back(a);
    }
    dfs(1,-1);
	
	for(auto&v:g[rt]){
		++idx;
		getson(v,rt);
	}
	priority_queue<array<int,2>> q;
	for(int i=1;i<=idx;i++) q.push({G[i].size(),i});
	
	while(q.size()>1){
		auto [_1,idx1]=q.top(); q.pop();
		auto [_2,idx2]=q.top(); q.pop();
		cout << G[idx1].back() << ' ' << G[idx2].back() << endl;
		G[idx1].pop_back();
		if(!G[idx1].empty()) q.push({G[idx1].size(),idx1});
		G[idx2].pop_back();
		if(!G[idx2].empty()) q.push({G[idx2].size(),idx2});
	}
	while(!q.empty()){
		auto [_,idx]=q.top(); q.pop();
		cout << G[idx].back() << ' ' << rt << endl;
	}
	cout << endl;
    return ;
}
signed main ()

G - Count Substring Query

本题题目显而易见就是求一个字符串中某一个串出现的次数明显的使用ac自动机即可

#include <bits/stdc++.h>
using namespace std;
const int N=1000010,M=210;
int tr[N][26],cnt[N],idx;
int ne[N],q[N],f[N],id[N];
int t,n;
string s; 
void insert(string s){
    int p=0;
    for(int i=0;s[i];i++)
    {
        int u=s[i]-'a';
        if(!tr[p][u]) tr[p][u]=++idx;
        p=tr[p][u];
        f[p]++;
    }
}
void insert(int x)
{
    int p=0;
    for(int i=0;s[i];i++)
    {
        int u=s[i]-'a';
        if(!tr[p][u]) tr[p][u]=++idx;
        p=tr[p][u];
    }
    id[x]=p;
}

void build()
{
    int hh=0,tt=-1;
    for(int i=0;i<26;i++)
    if(tr[0][i]) q[++tt]=tr[0][i];
    
    while(hh<=tt)
    {
        int t=q[hh++];
        
        for(int i=0;i<26;i++)
        {
            int p=tr[t][i];
            if(!p) tr[t][i]=tr[ne[t]][i];
            else 
            {
                ne[p]=tr[ne[t]][i];
                q[++tt]=p;
            }
        }
    }
}

int main ()
{
    cin>>s;
    insert(s);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>s;
        insert(i);
    }
    build();
    for(int i=idx-1;i>=0;i--) f[ne[q[i]]]+=f[q[i]];
    for(int i=1;i<=n;i++) cout<<f[id[i]]<<endl;
    
    return 0;
}

相关文章