abc247_a
题目翻译
一个字符串，输出向左移 $1$ 位的结果，第四个位置移完后消失。
题目思路
直接输出前一个位置。
AC 代码
void solve()
{
char c1,c2,c3,c4;
cin>>c1>>c2>>c3>>c4;
cout<<0<<c1<<c2<<c3<<endl;
}abc247_b
题目翻译
输入 $n$ 个人的姓和名，每个人的昵称是自己的姓或名，不能出现自己的昵称与其他人的姓或名相同。问是否可以做到。
题目思路
把姓名存进一个 multiset 里，自己的姓名一样只存一次。看自己的姓名是否出现 $>1$ 次。
AC 代码
string fir[105],sec[105];
multiset<string>name;
void solve()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>fir[i]>>sec[i];
if(fir[i]==sec[i])
{
name.insert(fir[i]);
}
else
{
name.insert(fir[i]);
name.insert(sec[i]);
}
}
for(int i=1;i<=n;i++)
{
if(name.count(fir[i])>1&&name.count(sec[i])>1)
{
puts("No");
return;
}
}
puts("Yes");
}abc247_c
题目翻译
已知 $s_1=\text{1}$。
之后 $s_x=s_{x-1}+x+s_{x-1}$。
例如 $s_2=\text{1 2 1}$
题目思路
按题意模拟即可，就是个基础的动态规划。
AC 代码
string s[20];
void solve()
{
s[1]="1";
int n;
cin>>n;
for(int i=2;i<=n;i++)
{
s[i]=s[i-1]+" "+to_string(i)+" "+s[i-1];
}
cout<<s[n]<<endl;
}abc247_d
题目翻译
维护一个队列。
1 x c 表示队尾插入 $x$ 个 $c$。
1 c 表示输出队首前 $c$ 的元素和，并出队。
题目思路
不能按题意模拟，超时。
队列里每个位置记录两个量，元素和个数。
每次输出就看个数。
AC 代码
struct node
{
int cnt,val;
};
queue<node>q;
void solve()
{
int query;
cin>>query;
while(query--)
{
int qq;
cin>>qq;
if(qq==1)
{
int x,c;
cin>>x>>c;
node z;
z.cnt=c;
z.val=x;
q.push(z);
}
else
{
int c;
long long sum=0;
cin>>c;
while(c>0)
{
if(q.front().cnt>c)
{
sum+=1LL*c*q.front().val;
q.front().cnt-=c;
break;
}
else
{
sum+=1LL*q.front().cnt*q.front().val;
c-=q.front().cnt;
q.pop();
}
}
cout<<sum<<endl;
}
}
}abc247_e
题目翻译
输入一个长度为 $n$ 个数字，还有 $X$ 和 $Y$。
问数组中有几个区间最大值是 $X$ 且最小值是 $Y$。
题目思路
所有数字分为 $a_i>Y$，$a_i=Y$，$a_i<X$，$a_i=X$，$X<a_i<Y$ 五种情况。
$>Y$ 和 $<X$ 的位置一定不能选。
选一个区间，包含至少一个 $=Y$，包含至少一个 $=X$，问有多少种方案。
问以每个位置作为结尾，有多少个方案。
对于每个位置，找自己之前的最近的 $X$ 是多少，最近的 $Y$ 是多少，至多选多少个数字没有 $>Y$ 和 $<X$ 的情况。
AC 代码
void solve()
{
int n,x,y,maxxid=0,minnid=0,la=1;
long long ans=0;
cin>>n>>x>>y;
for(int i=1;i<=n;i++)
{
int z;
cin>>z;
if(z==x)
{
maxxid=i;
}
if(z==y)
{
minnid=i;
}
if(z>x||z<y)
{
maxxid=0;
minnid=0;
la=i+1;
}
if(maxxid!=0&&minnid!=0)
{
ans+=min(maxxid,minnid)-la+1;
}
}
cout<<ans<<endl;
}abc247_f
题目翻译
有 $n$ 张牌，第 $i$ 张牌正面是 $P_i$，反面是 $Q_i$。保证 $P_i$和 $Q_i$ 是 $1$ 到 $n$ 的排列。
从所有的牌中选一个子集，使得从 $1$ 到 $n$ 的每个数字，都出现过（正面或反面） 。
题目思路
把每张牌看做是连接 $P_i$ 和 $Q_i$ 的一条边。
因为都是排列，整个图是由若干环组成的。
对每个换来说，选一个子集，不能有连续的两条边不选。
答案是 Lucas Number。
不同环不互相影响，不同环的答案撑起来就可以了。
AC 代码
const int mod=998244353;
int f[200050];
int c[200050];
int p[200050];
int q[200050];
int g[200050]={2,1};
long long z=1;
int F(int x)
{
return f[x]!=x?f[x]=F(f[x]):x;
}
void U(int x,int y)
{
x=F(x);
y=F(y);
if(x==y)
{
return;
}
f[x]=y;
c[y]+=c[x];
}
void solve()
{
int n;
cin>>n;
for(int i=2;i<=n;i++)
{
g[i]=(g[i-1]+g[i-2])%mod;
}
for(int i=1;i<=n;i++)
{
f[i]=i;
c[i]=1;
}
for(int i=1;i<=n;i++)
{
cin>>p[i];
}
for(int i=1;i<=n;i++)
{
cin>>q[i];
U(p[i],q[i]);
}
for(int i=1;i<=n;i++)
{
if(f[i]==i)
{
z=z*g[c[i]]%mod;
}
}
cout<<z<<endl;
}