1025模拟赛（兔子场）
感谢兔子女王 & 兔子公主不杀之恩。
A 「AGC008C」 Tetromino Tiling
题意
\(~~~~\) 七种俄罗斯方块，已知每种的数量，（按照形状记为 \(\text{I,O,T,L,J,S,Z}\)）求最多可以使用其中的多少块使得选出的块可以恰好摆成一个宽为 \(2\) 的长方形。
每种方块数量 \(\leq 10^9\).
题解
\(~~~~\) 注意到选择 \(\text{S,Z,T}\) 必然会在两边产生奇数的空位，这是无法被填补的，所以这三种必然不能使用。
\(~~~~\) 然后考虑 \(\text{I,L,J}\) 形可以每两个组成一个长方形，\(\text{O}\) 形可以一个组成长方形，都是非常优秀的。但是注意到各选 \(1\) 个 \(\text{I,L,J}\) 可以组成一个长为 \(6\) 的长方形。而如果摆放两个那其实我们可以把它们拆成各自与自己组合。
\(~~~~\) 所以我们枚举是否放置这个长为 \(6\) 的长方形然后两种情况取 \(\max\) 即可。
代码
查看代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
template<typename T>void read(T &x)
{
T f=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9') {x=x*10+s-'0';s=getchar();}
x*=f;
}
int a[10];
int main() {
freopen("what.in","r",stdin);
freopen("what.out","w",stdout);
int T;read(T);
while(T--)
{
for(int i=1;i<=7;i++) read(a[i]);
ll Ans1=0,Ans2=0;
Ans1+=a[1]/2*2; Ans1+=a[2]; Ans1+=a[4]/2*2; Ans1+=a[5]/2*2;
if((a[1]&1)&&(a[4]&1)&&(a[5]&1)) Ans1+=3;
if(a[1]&&a[4]&&a[5]) Ans2+=3,a[1]--,a[4]--,a[5]--;
Ans2+=a[1]/2*2; Ans2+=a[2]; Ans2+=a[4]/2*2; Ans2+=a[5]/2*2;
printf("%lld\n",max(Ans1,Ans2));
}
return 0;
}
/*
清夜无尘。月色如银。酒斟时、须满十分。浮名浮利，虚苦劳神。叹隙中驹，石中火，梦中身。
虽抱文章，开口谁亲。且陶陶、乐尽天真。几时归去，作个闲人。对一张琴，一壶酒，一溪云。
*/
B 「AGC008D」 K-th K
题意
\(~~~~\) 构造一个数列，包含 \(n\times n\) 个数，使得每个 \(1\sim n\) 内的数在其中出现 \(n\) 次且 \(i\) 第 \(i\) 次出现的位置为 \(p_i\)。
\(~~~~\) \(1\leq n\leq 2000\).
题解
\(~~~~\) 兔子公主数据造水了于是AT上WA了3但是我过了！
\(~~~~\) 考虑某个数第 \(i\) 次出现在 \(p_i\) 那么 \([1,p_i-1]\) 就会出现 \(i-1\) 次这个数，\([p_i+1,n]\) 就会出现 \(n-i\) 次这个数。
\(~~~~\) 现在我们的想法是把最难放的先放置好，也就是选择 \(p_i\) 最小的那个 \(i\) 然后往前面 \(i-1\) 个空格放 \(i\) 。同理选择 \(p_j\) 最大的那个 \(j\) 然后在后面 \(n-j\) 个空格放 \(j\) 。
\(~~~~\) 但是需要注意一些细节的问题不然就会被AT背刺。
代码
查看代码
#include <bits/stdc++.h>
using namespace std;
template<typename T>void read(T &x)
{
T f=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9') {x=x*10+s-'0';s=getchar();}
x*=f;
}
template<typename T>void print(T x) {
if(x<0) putchar('-'),x=-x;
if(x>9) print(x/10);
putchar(x%10+'0');
}
int x1[2005],x2[2005],arr[4000005];
int main() {
// freopen("treasure.in","r",stdin);
// freopen("treasure.out","w",stdout);
int n;read(n);
for(int i=1;i<=n;i++) read(x1[i]),arr[x2[i]=x1[i]]=i;
x1[0]=1e9;
int L=1,R=n*n,tot=0;
while(L<=R)
{
int MinPos=0,MaxPos=0;
for(int i=1;i<=n;i++)
{
if(x1[i]!=1e9&&x1[MinPos]>x1[i]) MinPos=i;
if(x2[i]!=1e9&&x2[MaxPos]<x2[i]) MaxPos=i;
}
int cnt=MinPos-1,Val=MinPos;
int Tmp=cnt;
// cerr<<"Min"<<L<<" "<<R<<" "<<cnt<<" "<<Val<<endl;
while(cnt)
{
while(arr[L]) L++;
arr[L]=Val;cnt--;
}
if(L>x1[MinPos]&&(Tmp!=0||arr[L-1]!=Val)){return puts("No")&0;}
cnt=n-MaxPos,Val=MaxPos;
Tmp=cnt;
// cerr<<"Max"<<L<<" "<<R<<" "<<cnt<<" "<<Val<<endl;
while(cnt)
{
while(arr[R]) R--;
arr[R]=Val;cnt--;
}
// cerr<<R<<" "<<x2[MaxPos]<<endl;
if(R<x2[MaxPos]&&(Tmp!=0||arr[R+1]!=Val)){return puts("No")&0;}
x1[MinPos]=1e9; x2[MaxPos]=1e9;
while(arr[L]) L++;
while(arr[R]) R--;
}
puts("Yes");
for(int i=1;i<=n*n;i++) print(arr[i]),putchar(' ');
return 0;
}
/*
清夜无尘。月色如银。酒斟时、须满十分。浮名浮利，虚苦劳神。叹隙中驹，石中火，梦中身。
虽抱文章，开口谁亲。且陶陶、乐尽天真。几时归去，作个闲人。对一张琴，一壶酒，一溪云。
*/
C 「AGC008F」 Black Radius
题意
\(~~~~\) 求每个关键点和其距离为 \(d\geq0\) 的点组成的集合的不同种类。距离用边来表示。
\(~~~~\) \(1\leq n\leq 2\times 10^5\).
题解
\(~~~~\) 用 \(f(u,d)\) 表示与 \(u\) 相距为 \(d\) 的点的集合。
\(~~~~\) 那么我们希望的是我们可以对每个点唯一统计哪些 \(d\) 是合法的，也就是对于 \(u\) 合法的最小的那些 \(d\) 的区间。
\(~~~~\) 由于全集很容易算重，所以先把这个东西剔掉最后加回来。
\(~~~~\) 先假设每个点都是关键点，那么记距离 \(u\) 最远的点的距离为 \(dis_1\) ，则应该有 \(d<dis_1\)，这样不会覆盖全集。
\(~~~~\) 同时我们还注意到如果对于一个点 \(x\) 有 \(f(x,d)=f(y,d-1)\)，其中 \(y\) 为其一个相邻结点。这种情况也是无法忍受的,那么在这种情况下 \(v\) 应该取相邻的子树中 \(v\) 最深的那个。所以我们要求这个 \(v\) 仍不合法就应该取 \(d\leq dis_2+1\)，其中 \(dis_2\) 为相邻的树当中次深的那一个。
\(~~~~\) 那么综上 \(d < \min{t+2,dis_1}\)。
\(~~~~\) 现在来考虑如果不是每个点都是关键点，那么我们对非关键点就会把其可取的区间下界缩小到其最浅的具有关键点的子树深度。这样我们试想圆心从那个关键点移动到非关键点才能覆盖完整棵子树。所以我们也求出了下界。然后我们换根求解即可。
代码
查看代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
template<typename T>void read(T &x)
{
T f=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9') {x=x*10+s-'0';s=getchar();}
x*=f;
}
char S[200005];
vector <int> G[200005];
int Dis1[200005],Dis2[200005],Low[200005],siz[200005];
void dfs1(int u,int fa)
{
if(S[u]=='1') siz[u]=1;
else Low[u]=1e9;
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
if(v==fa) continue;
dfs1(v,u); siz[u]+=siz[v];
if(Dis1[v]+1>Dis1[u]) Dis2[u]=Dis1[u],Dis1[u]=Dis1[v]+1;
else if(Dis1[v]+1>Dis2[u]) Dis2[u]=Dis1[v]+1;
if(siz[v]) Low[u]=min(Low[u],Dis1[v]+1);
}
}
ll Ans;
void dfs2(int u,int fa)
{
Ans+=max(0,min(Dis2[u]+2,Dis1[u])-Low[u]);
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
if(v==fa) continue;
int Up=(Dis1[u]==Dis1[v]+1)?(Dis2[u]+1):(Dis1[u]+1);
if(Up>Dis1[v]) Dis2[v]=Dis1[v],Dis1[v]=Up;
else if(Up>Dis2[v]) Dis2[v]=Up;
if(siz[1]-siz[v]) Low[v]=min(Low[v],Up);
dfs2(v,u);
}
}
int main() {
// freopen("fire.in","r",stdin);
// freopen("fire.out","w",stdout);
int n;read(n);
for(int i=1,u,v;i<n;i++)
{
read(u);read(v);
G[u].push_back(v);
G[v].push_back(u);
}
scanf("%s",S+1);
dfs1(1,0);dfs2(1,0);
printf("%lld",Ans+1);
return 0;
}
/*
清夜无尘。月色如银。酒斟时、须满十分。浮名浮利，虚苦劳神。叹隙中驹，石中火，梦中身。
虽抱文章，开口谁亲。且陶陶、乐尽天真。几时归去，作个闲人。对一张琴，一壶酒，一溪云。
*/
D 「AGC011F」 Train Service Planning
不会
标签：1025,Dis1,Dis2,int,兔子,leq,Low,模拟,getchar From： https://www.cnblogs.com/Azazel/p/16826131.html