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;
}
- Contest Programming Beginner AtCoder UNIQUEcontest programming beginner atcoder contest programming securities beginner contest programming beginner registry contest programming beginner keyence contest programming beginner systems beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332