526互联

UNIQUE VISION Programming Contest 2023 New Year (AtCoder Beginner Contest 287) ABCDE

发布时间 2023-06-12 19:49:12作者: nannan4128

UNIQUE VISION Programming Contest 2023 New Year (AtCoder Beginner Contest 287)

A - Majority

Problem Statement

题意：给你n个字符串，字符串是 For 表示agree，字符串 Against表示disagree，让你判断最终是否通过。

Solution

思路：统计 For 和 Against的数量，比较一下即可。

#include<bits/stdc++.h>
using namespace std;
string s1 = "For",s2 = "Against";
int main()
{
	int n;
	cin>>n;
	int cnt1 = 0,cnt2 = 0;
	for(int i = 1;i<=n;i++)
	{
		string s;
		cin>>s;
		if(s==s1)cnt1++;
		else cnt2++;
	}
	if(cnt1>cnt2)cout<<"Yes\n";
	else cout<<"No\n";
	return 0;
}

B - Postal Card

Problem Statement

题意：给你n个长度为6的串和m个长度为3的串，让你把n个长度为6的串的后三位截取下来去和那m个

长度为3的串进行匹配，如果截取下来的串能和那m个中有>=1个是一样的，那就算是匹配，外面需要

统计匹配的个数。

Solution

思路：按照题意截取后n个串的后三位，再把那m个串放入set,把那n个串for一遍找set里面有没有一样的，有就ans++。

#include<bits/stdc++.h>
using namespace std;
set<string>s;
vector<string>v;
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i = 1;i<=n;i++)
	{
		string x;
		cin>>x;
		x = x.substr(3,3);
		v.push_back(x);
	}
	int ans = 0;
	for(int i = 1;i<=m;i++)
	{
		string x;
		cin>>x;
		s.insert(x);
	}
	for(auto x:v)
	{
		//cout<<x<<" "<<s.count(x)<<endl;
		if(s.count(x))ans++;
	}
	cout<<ans<<endl;
	return 0;
}

/*
5 4
235983
109333
823467
592801
000333
333
108
467
983

*/

C - Path Graph?

Problem Statement

题意：给你一个简单无向图，n个点m条边。让你判断是不是路径图。

路径图：没有环或支链，就是一条单链

Solution

思路：首先是一条单链，那先判断连通性，判断完之后再去看入度和出度。

因为是单链，那只存在一个入度和出度为0的点，且其他点的入度=出度=1。

如果上述两个条件均满足则输出 Yes ，否则 No 。
注意：判断连通性！！！如果不判的话可能满足了后面的度的条件但不连通。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int ind[N],outd[N];
vector<int>edge[N*2];
bool vis[N];
void dfs(int x,int fa)
{
	vis[x] = true;
	for(auto y:edge[x])
	{
		if(y==fa||vis[y])continue;
		dfs(y,x);
	}
}
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i = 1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		edge[x].push_back(y);
		edge[y].push_back(x);
		outd[x]++,ind[y]++;
		ind[x]++,outd[y]++;
	}
	dfs(1,0);
	for(int i = 1;i<=n;i++)
	{
		if(!vis[i])
		{
			cout<<"No\n";
			return 0;	
		}
	}
	int cnt1 = 0,cnt2 = 0,cnt3 = 0;
	for(int i = 1;i<=n;i++)
	{
		if(outd[i]==1)cnt1++;
		if(ind[i]==1)cnt2++;
		if(outd[i]==ind[i]&&outd[i]==2)cnt3++;
	}
	//cout<<cnt1<<" "<<cnt2<<" "<<cnt3<<endl;
	if(cnt1==2&&cnt2==2&&cnt3==n-2)
		cout<<"Yes\n";
	else  cout<<"No\n";
	return 0;
}

D - Match or Not

Problem Statement

题意：给你两个串S和T，只包含小写字母和？,且|S|>|T|。

我们现在要做的是判断匹配问题，取S的前x个和S的(|T|-x)个串起来，看看是不是和T串匹配，

如果是?的可以变成你想要变成的。

Solution

思路：我们利用前缀和的思想对前缀和后缀进行一个可行性的判断。

如果前x个不满足则前x+1个一定不满足，同理后x个不满足，后x+1个也同样不满足，根据这个思路

我们对S串进行预处理，这样的话后面询问的时间复杂度就说O(1)啦。

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10;
bool pre[N],suf[N];
int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	string s,t;
	cin>>s>>t;
	int n = s.size(),m = t.size();
	s = "?"+s,t = "?"+t;
	pre[0] = true;
	for(int i  = 1;i<=m;i++)
	{		
		if((s[i]==t[i]||s[i]=='?'||t[i]=='?')&&pre[i-1])
			pre[i] = true;
		else pre[i] = false;
	}
	
	reverse(s.begin(), s.end());
	reverse(t.begin(),t.end());
	suf[0] = true;
	s = "?"+s;
	t = "?"+t;
	for(int i  = 1;i<=m;i++)
	{		
		if((s[i]==t[i]||s[i]=='?'||t[i]=='?')&&suf[i-1])
			suf[i] = true;
		else suf[i] = false;
	}

	for(int i = 1;i<=n;i++)
	{
		if(i-1>m)break;
		if(pre[i-1]&&suf[m-(i-1)])cout<<"Yes\n";
		else cout<<"No\n";
	}
	return 0;
}

/*
aa
b


?a
b
*/

E - Karuta

Problem Statement

题意：给你n个串，均由小写字母组成。去计算\(maxLCP(Si,Sj)\)

Solution

思路：

虽然但是，看到最长公共前缀，应该很容易想到是个Trie的板子，正解也就是Trie树了。当然hash或者排序之后搞一搞也是可以的。

法一：排序+前后比较。

现根据字典序对n个串sort一下，即按照字典序排序，这样的话和它匹配度最大的就是它的前一个或者后一个，进行比较取max就是答案。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5+10;

int main()
{
    int n;
    cin>>n;
    vector<pair<string ,int>>s(n);
    for(int i = 0;i<n;i++)
        cin>>s[i].first,s[i].second = i;
    sort(s.begin(), s.end());
    // for(auto x:s)
    //     cout<<x.first<<" "<<x.second<<endl;
    vector<int>ans(n);
    for(int i = 0;i<n-1;i++)
    {
        string a = s[i].first;
        string b = s[i+1].first;
        //cout<<"a = "<<a<<" b = "<<b<<endl;
        int l1 = a.size(),l2 = b.size();
        int cur = 0;
        while(cur<l1&&cur<l2)
        {
            if(a[cur]!=b[cur])break;
            cur++;
        }
        //cout<<"cur = "<<cur<<endl;
        ans[s[i].second] = max( ans[s[i].second],cur);
        ans[s[i+1].second] = max(ans[s[i+1].second],cur);
    }
    for(int i = 0;i<n;i++)
        cout<<ans[i]<<endl;
    return 0;
}

法二：hash，对每个串hash一下，枚举前缀长度用map记录一下，不要用string映射会炸，用hash值去映射，做完预处理之后呢，我们对这n个串for一遍，倒着枚举长度，看该值在mp里面出现次数是不是>=2的，是的话就是答案，我们break掉输出答案即可。

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

#define int long long 
typedef pair<int, int> PII;
const int N = 5e5+10;
struct DoubleStringHash
{
    // #define int long long 
    vector<int> h1, h2, w1, w2;
    int base1 = 131, base2 = 13331;
    int p1 = 1e9+7, p2 = 1e9+9;
    void init(string s) {
        int len = s.size();
        s = " " + s;
        h1.resize(len + 1), w1.resize(len + 1);
        h2.resize(len + 1), w2.resize(len + 1);
        h1[0] = 0, w1[0] = 1;
        h2[0] = 0, w2[0] = 1;
        for(int i = 1; i <= len; i++) {
            h1[i] = (h1[i - 1] * base1 + s[i]) % p1, w1[i] = w1[i-1] * base1 % p1;
            h2[i] = (h2[i - 1] * base2 + s[i]) % p2, w2[i] = w2[i-1] * base2 % p2;
        }
    }
    pair<int, int> get(int l, int r) {
        return {(h1[r] - h1[l - 1] * w1[r - l + 1] % p1 + p1) % p1, (h2[r] - h2[l - 1] * w2[r - l + 1] % p2 + p2) % p2};
    }
}ha;

string s[N];
map<pair<int,int>,int>mp;
signed main()
{
    std::ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int n;
    cin>>n;
    for(int i = 1;i<=n;i++)
    {
        cin>>s[i];
        ha.init(s[i]);
        int sz = s[i].size();
        for(int j = 1;j<=sz;j++)
            mp[ha.get(1,j)]++;
    }
    for(int i = 1;i<=n;i++)
    {
        int pos = 0;
        ha.init(s[i]);
        int sz = s[i].size();
        for(int j = sz;j>=1;j--)
        {
            if(mp[ha.get(1,j)]>=2)
            {
                pos = j;
                break;
            }
        }
        cout<<pos<<'\n';
    }
    
    return 0;
}

法三:Trie树，这就是Trie树的模板题了，毕竟Trie树就是用公共前缀的这个思想去写的，那我们只需要再次基础上记录一下每个节点的出现次数，同样出现次数>=2的对res++。

#include<bits/stdc++.h>
using namespace std;
struct trie 
{
 int nxt[500010][26], cnt;
 bool isend[500010];  // 该结点结尾的字符串是否存在
int c[500010];
 void insert(string s) {  // 插入字符串
     int now = 0;
     int l = s.size();
     for(int i = 0; i < l; i++) 
     {
         int x = s[i] - 'a';
         if(!nxt[now][x]) nxt[now][x] = ++cnt;  // 如果没有，就添加结点
         now = nxt[now][x];
        c[now]++;
     }
     isend[now] = 1;
 }

 bool find(string s) {  // 查找字符串
     int now = 0;
     int l = s.size();
     for(int i = 0; i < l; i++) {
         int x = s[i] - 'a';
         if(!nxt[now][x]) return 0;
         now = nxt[now][x];
     }
     return isend[now];
 }

 int maxLCP(const string&s)
 {
    int res = 0;
    int l = s.size();
    int now = 0;
    for(int i = 0;i<l;i++)
    {
        int x = s[i]-'a';
        if(!nxt[now][x])return 0;
        now = nxt[now][x];
        if(c[now]>=2)++res;
    }
    return res;
 }
}tr;


int main()
{
    int n;
    cin>>n;
    vector<string>s(n);
    for(int i = 0;i<n;i++)
    {
        cin>>s[i];
        tr.insert(s[i]);
    }
    for(int i = 0;i<n;i++)
    {
        cout<<tr.maxLCP(s[i])<<"\n";
    }
    return 0;
}