本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-27 13:51:57
自己做出了 ABCDE，F 是个什么玩意啊。
A
如果忽略 $c$，那么 $a,b$ 无论如何可以匹配。
只要有一个位置可以在匹配 $a,b$ 的情况下不匹配 $c$，那么有解。
#include <bits\/stdc++.h>
using namespace std;
int T;
const int maxn=25;
char a[maxn],b[maxn],c[maxn];
int n;
void solve()
{
scanf("%d",&n);
scanf("%s",a+1);
scanf("%s",b+1);
scanf("%s",c+1);
bool flag2=0;
for(int i=1;i<=n;i++)
{
if(a[i]==b[i])
{
if(c[i]!=a[i])
{
flag2=1;
}
}
else
{
if(a[i]!=c[i]&&b[i]!=c[i])
{
flag2=1;
}
}
}
puts(flag2?"YES":"NO");
}
int main()
{
scanf("%d",&T);
while(T--)
{
solve();
}
return 0;
}
B
按照枚举三角形最长边长度考虑。
显然最长边在三角形中出现次数大于等于两次。
然后推个柿子就行了。
#include <bits\/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3e5+5;
int t,n;
int a[maxn];
int cnt[maxn];
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
cnt[a[i]]++;
}
ll ans=0;
ll pre=0;
for(int i=0;i<=n;i++)
{
ans+=max(0ll,1ll*cnt[i]*(cnt[i]-1)*(cnt[i]-2)\/6ll);
if(i!=0)
{
ans+=max(0ll,1ll*cnt[i]*(cnt[i]-1)*pre\/2ll);
}
pre+=cnt[i];
}
printf("%lld\n",ans);
\/\/ clean
for(int i=0;i<=n;i++)cnt[i]=0;
}
return 0;
}
C
预处理正向和反向的捷径数量的前缀和。
#include <bits\/stdc++.h>
using namespace std;
typedef long long ll;
int T;
const int maxn=1e5+5;
int n,m;
int a[maxn];
ll tagpre[maxn],tagsuf[maxn];\/\/ 在到达他之前经过了多少个捷径
void solve()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
a[0]=-1e9;
a[n+1]=2e9+1;
for(int i=1;i<=n;i++)
{
if(a[i]-a[i-1]<a[i+1]-a[i])
{
tagsuf[i-1]+=(a[i]-a[i-1]-1);
}
else
{
tagpre[i+1]+=(a[i+1]-a[i]-1);
}
}
for(int i=1;i<=n;i++)
{
tagpre[i]+=tagpre[i-1];
}
for(int i=n-1;i>=1;i--)
{
tagsuf[i]+=tagsuf[i+1];
}
scanf("%d",&m);
while(m--)
{
int x,y;
scanf("%d%d",&x,&y);
if(x<y)
{
printf("%lld\n",a[y]-a[x]-tagpre[y]+tagpre[x]);
}
else
{
swap(x,y);
printf("%lld\n",a[y]-a[x]-tagsuf[x]+tagsuf[y]);
}
}
\/\/ clean
for(int i=0;i<=n+1;i++)
{
tagpre[i]=0;
tagsuf[i]=0;
}
}
int main()
{
scanf("%d",&T);
while(T--)
{
solve();
}
return 0;
}
D
注意，如果上一轮某一个 mob 及他的的左右邻居都还活着，那么他这一轮仍然活着，因为每一轮生命重置。综上，其实每一轮只需要考虑上一轮被击杀的怪的邻居（当然，不考虑已被击杀的怪）。
于是用链表维护存活的 monster。
然后先构建一个队列 qd，存放所有可能造成击杀的 monster，初始设置为全部 monster 加入。
每一轮依次进行一下操作：
- 遍历可能造成影响的 monster 队列 qd，并统计被伤害的 monster 有哪些，以及分别受到的伤害，将所有受到伤害的 monster 加入队列 wait。
- 遍历所有受到伤害的 monster 队列 wait，对于被杀死的 monster，将其从链表删除并加入队列 death。
- 遍历队列 death，将其存活的邻居加入集合 qd2
- 为了下一轮统计完整，遍历 qd2，将其存活邻居集合 qd3
- 合并 qd2,qd3，并将 qd 替换为 qd2 和 qd3 的并集。
#include <bits\/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
int T;
const int maxn=3e5+5;
int n;
int a[maxn],d[maxn];
struct List
{
int lef[maxn],rig[maxn];
void rebuild()
{
FOR(i,1,n)
{
lef[i]=i-1;
}
FOR(i,1,n-1)
{
rig[i]=i+1;
}
rig[n]=rig[n+1]=0;
lef[0]=lef[n+1]=0;
}
void del(int pos)
{
rig[lef[pos]]=rig[pos];
lef[rig[pos]]=lef[pos];
}
}lst;
ll dam[maxn];
bool dead[maxn];
\/*
hack.in:
1
4
1 1 1 2
1 2 1 1
hack.out
1 1 1 0
(heal 1,dam 1),(heal 2,dam 1),(heal 1,dam 2)
*\/
void solve()
{
scanf("%d",&n);
FOR(i,1,n)
{
scanf("%d",&d[i]);
}
FOR(i,1,n)
{
scanf("%d",&a[i]);
}
\/\/ 按照我的习惯，d=damage=攻击
lst.rebuild();
queue<int> qd,death;
set<int> wait,qd2,qd3;
FOR(i,1,n)
{
qd.push(i);
}
FOR(rounds,1,n)
{
\/\/ printf("\n round %d\n",rounds);
while(!qd.empty())
{
int u=qd.front();
\/\/ printf("u = %d\n",u);
\/\/ printf("lef = %d rig = %d\n",lst.lef[u],lst.rig[u]);
if(lst.lef[u])
{
dam[lst.lef[u]]+=d[u];
wait.insert(lst.lef[u]);
}
if(lst.rig[u])
{
dam[lst.rig[u]]+=d[u];
wait.insert(lst.rig[u]);
}
qd.pop();
}\/\/ 计算攻击
int cntdeath=0;
for(int u:wait)
{
\/\/\/ printf("dam[%d] = %d\n",u,dam[u]);
if(dam[u]>a[u])
{
lst.del(u);
death.push(u);
\/\/ printf("death = %d,dam = %d\n",u,dam[u]);
cntdeath++;
dead[u]=1;
}
dam[u]=0;
}\/\/ 处理死亡
wait.clear();
while(!death.empty())
{
int u=death.front();
death.pop();
if(lst.lef[u])qd2.insert(lst.lef[u]);
if(lst.rig[u])qd2.insert(lst.rig[u]);
}\/\/ 将死亡的mob 的邻居加入
for(int v:qd2)
{
if(!dead[v])
{
if(lst.lef[v])qd3.insert(lst.lef[v]);
if(lst.rig[v])qd3.insert(lst.rig[v]);
}
}
for(int v:qd2)if(!dead[v])qd3.insert(v);
for(int v:qd3)if(!dead[v])qd.push(v);
qd2.clear();
qd3.clear();
printf("%d ",cntdeath);
}
FOR(i,1,n)dead[i]=0;
printf("\n");
}
int main()
{
scanf("%d",&T);
while(T--)
{
solve();
}
return 0;
}
E
先将 $X$ 减一，这样只需要统计非空子序列了。
注意，一个长度为 $n$ 的上升子序列造成的贡献是 $2^n -1$，初步考虑从大到小依次构造不同长度的上升序列（注意，需要满足互相不影响），最终使得总贡献为 $X$。
但是需要注意，长度限制是 $200$，如果这样构造，那么总长度是 $O(log_2^2 n)$ 的，无法通过。
这时候，考虑一些数列之间进行共用。
此时，可以想到，先构造一个最大的上升序列 base 使得贡献不超过 $X$，然后让相邻元素差的很大以留出充足预备空间，然后，在后面降序插入数组，每插入一个数字 $x$，设序列 base 前 $id$ 个数字小于 $x$，那么总贡献将增加 $2^{id}$，这样就可以根据二进制完成构造了。
#include <bits\/stdc++.h>
using namespace std;
const int maxn=205;
typedef long long ll;
int T;
ll ans[maxn];
ll ar[maxn];
void solve()
{
ll x;
scanf("%lld",&x);
x--;
if(lower_bound(ans+1,ans+63,x)-ans==64)
{
puts("-1");
return;
}
int unti=upper_bound(ans+1,ans+63,x)-ans-1;
if(unti==64)
{
puts("-1");
return;
}
x-=ans[unti];
\/\/printf("unti = %d\n",unti);
ar[1]=1;
for(int i=2;i<=unti;i++)
{
ar[i]=ar[i-1]+1000;
}
int id=unti;
while(x)
{
\/\/ printf("id = %d x = %lld\n",id,x);
while(ans[id]+1>x)id--;
x-=(ans[id]+1);
ar[++unti]=ar[id]+1;
}
printf("%d\n",unti);
for(int i=1;i<=unti;i++)
{
printf("%d ",ar[i]);
}
printf("\n");
}
int main()
{
ans[0]=0;
for(int i=1;i<=63;i++)
{
ans[i]=(unsigned long long)(ans[i-1]+1)*2ll-1ll;
}
scanf("%d",&T);
while(T--)
{
solve();
}
return 0;
}
F
暂时没想出来。
鲁ICP备2025150228号