2024 United Kingdom and Ireland Programming Contest (AIKL)
好久没更新题解了（其实我有偷偷更新那个dp的） 这段时间偷偷上了个蓝 然后这一场是vp的英国区域赛 虽然是区域赛而且cf上标记的是四颗星但我真的感觉只有省赛难度 接下来的目标应该是跟着队友把今年赛季的gym都vp一遍
哦对了 封面图是我自己用ai搓的 最近也炼了不少的丹
A. Amalgram
题意
给两个字符串，输出一个每个字符出现次数都大于原本两个字符串出现次数最大值的最短的字符串
思路
开个桶记录一下 然后输出就完了呗
代码
#include <bits/stdc++.h>
#define maxOf(a) *max_element(a.begin(),a.end())
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
void solve()
{
string a,b;
cin>>a>>b;
int st1[26],st2[26];
memset(st1,0,sizeof(st1));
memset(st2,0,sizeof(st2));
for(auto r:a)
{
st1[r-'a']++;
}
for(auto r:b)
{
st2[r-'a']++;
}
for(int i=0;i<26;i++)
{
for(int j=0;j<max(st1[i],st2[i]);j++)
{
printf("%c",i+'a');
}
}
printf("\n");
}
int main()
{
int T=1;
// scanf("%d",&T);
while(T--)
{
solve();
}
return 0;
}
L. Leg Day
题意
给定n个字符串作为训练周期，第i个字符串如果包括rest说明这一天休息，如果出现leg说明这一天练腿，如果都没有说明练胳膊，输出一个月的日历表示每天训练什么
思路
最大难点反而在输出emoji 好在样例copy下来调一调也就知道了 不知道的看下面的代码也就知道了
代码
#include <bits/stdc++.h>
#define maxOf(a) *max_element(a.begin(),a.end())
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
void solve()
{
int n;
scanf("%d",&n);
vector<int> v;
while(n--)
{
string s;
cin>>s;
if(s.find("rest")<s.size())
{
v.push_back(0);
}
else if(s.find("leg")<s.size())
{
v.push_back(1);
}
else
{
v.push_back(2);
}
}
int idx=0,cnt=0;
while(cnt<31)
{
if(idx==v.size())
{
idx=0;
}
if(cnt%7==0)
{
printf("\n");
}
if(v[idx]==0)
{
printf("\U0001f60e");
}
else if(v[idx]==1)
{
printf("\U0001f9b5");
}
else
{
printf("\U0001f4aa");
}
idx++;
cnt++;
}
}
int main()
{
int T=1;
//scanf("%d",&T);
while(T--)
{
solve();
}
return 0;
}
K. Knitting
题意
用k种颜色的布匹组成一个长度为n的布，要求每k个连续的布匹中没有重复，给定前m个布匹，让你输出最终的布匹排序
思路
开一个优先队列 然后贪心往后添加 加不了就输出impossible
代码
#include <bits/stdc++.h>
#define maxOf(a) *max_element(a.begin(),a.end())
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
void solve()
{
int n,k,p;
scanf("%d%d%d",&n,&k,&p);
int m;
scanf("%d",&m);
vector<int> ans;
ans.push_back(-1);
for(int i=0;i<m;i++)
{
int x;
scanf("%d",&x);
ans.push_back(x);
}
int lst_pos[k+1],cnt[k+1];
memset(lst_pos,0,sizeof(lst_pos));
memset(cnt,0,sizeof(cnt));
for(int i=1;i<=m;i++)
{
if(lst_pos[ans[i]] and i-lst_pos[ans[i]]<p)
{
printf("impossible\n");
return ;
}
cnt[ans[i]]++;
lst_pos[ans[i]]=i;
}
priority_queue<pii,vector<pii>,greater<pii>> pq,allowed;
for(int i=1;i<=k;i++)
{
pq.push({lst_pos[i],i});
}
for(int i=m+1;i<=n;i++)
{
while(pq.size())
{
auto [pos,id]=pq.top();
if(i-pos>=p or pos==0)
{
pq.pop();
allowed.push({cnt[id],id});
}
else
{
break;
}
}
if(allowed.size())
{
auto [c,id]=allowed.top();
allowed.pop();
ans.push_back(id);
cnt[id]++;
lst_pos[id]=i;
pq.push({i,id});
}
else
{
printf("impossible\n");
return ;
}
}
for(int i=1;i<=n;i++) printf("%d ",ans[i]);
printf("\n");
}
int main()
{
int T=1;
//scanf("%d",&T);
while(T--)
{
solve();
}
return 0;
}
I. Inconsistent Patterns
题意
说是有一种很经典的悖论，如下
众所周知窝农有两个很强的队伍，分别是yzc队和奶龙队，他们今天分别做了一次训练，都包括图论和几何题，一共都是350题
yzc队完成了87道图论题中的81道（通过率为93%），263道几何题中的192道（通过率为73%），总通过率78%
奶龙队完成了270道图论题中的234道（通过率为87%），80道几何题中的55道（通过率为69%），总通过率83%非常amazing的事情发生了，奶龙队两种题目的通过率都没有yzc队高，但是最后却成功反杀
这就是有名的辛普森悖论，现在给你总题数为m，有n种类型的题目，构造一种情况满足上面的悖论
思路
首先有一个队要在分项中都比另外一个队高 然后另外一个队可以靠某一个项目占比特别大有过的特别多（但是比例还是要较小完成） 那就控制某一个是1 2，其他都是1 1就行了
代码
#include <bits/stdc++.h>
#define maxOf(a) *max_element(a.begin(),a.end())
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
void solve()
{
ll n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
if(i!=n and i!=1)
cout<<"1 1 1 2\n";
else if(i==1)
cout<<"1 1 "<<m-2*(n-1)-1<<' '<<m-2*(n-1)<<'\n';
else if(i==n)
{
int tmp;
if(m-(n-1)&1)
tmp=(m-(n-1)+1)/2;
else
tmp=(m-(n-1))/2+1;
cout<<tmp<<' '<<m-(n-1)<<" 1 2\n";
}
}
}
int main()
{
int T=1;
//scanf("%d",&T);
while(T--)
{
solve();
}
return 0;
}