Preface
补题，之前由于要准备开学考（其实只是临时抱佛脚罢了），所以好久没写题
不过索性学校题目简单，微积分线代C程都满绩了（甚至溢出好多），思政被卡了一分满绩点，而大英不出所料3.7/4.0
嘛不过我也不是很在意绩点的说，这个学期还是要把重心放在ACM上了
A1. Non-alternating Deck (easy version)&&A2. Alternating Deck (hard version)
反正都是暴力枚举，两道题的细节地方修改一下即可
A1-CODE
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int turn[4]={1,1,0,0};
int t,n;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; int sum=0,ans[2]={0,0}; for (scanf("%d",&n),i=1;sum<n;++i)
{
int tp=i==1?0:turn[(i-2)%4],x=min(i,n-sum); sum+=x; ans[tp]+=x;
}
printf("%d %d\n",ans[0],ans[1]);
}
return 0;
}
A2-CODE
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int turn[4]={1,1,0,0};
int t,n;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; int sum=0,ans[2][2]={0,0,0,0}; bool col=0;
for (scanf("%d",&n),i=1;sum<n;++i)
{
int tp=i==1?0:turn[(i-2)%4],x=min(i,n-sum); sum+=x;
ans[tp][col]+=(x+1)/2; ans[tp][col^1]+=x/2; col^=(x&1);
}
printf("%d %d %d %d\n",ans[0][0],ans[0][1],ans[1][0],ans[1][1]);
}
return 0;
}
B. Cake Assembly Line
不难发现我们对于每一对要配对的喷头和蛋糕，让它们成功配对的合法位移量一定是一个区间
因此把\(n\)个区间做个交集看看是否为空即可
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int t,n,w,h,a[N],b[N],L,R;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%d%d%d",&n,&w,&h),i=1;i<=n;++i) scanf("%d",&a[i]);
for (i=1;i<=n;++i) scanf("%d",&b[i]); L=-1e9; R=1e9;
for (i=1;i<=n;++i) L=max(L,(b[i]+h)-(a[i]+w)),R=min(R,(b[i]-h)-(a[i]-w));
puts(L<=R?"YES":"NO");
}
return 0;
}
C. Monsters (easy version)
接下来，我给大家展示一波教科书般的亵渎（bushi
首先不难发现亵渎肯定是最后放的，然后考虑我们需要用操作\(1\)将序列变成形如\(1,\cdots,2,\cdots,3,\cdots,t\)的形式（即若干个\(1\)，若干个\(2\)，直到若干个\(t\)）
因此我们可以依次枚举\(i\)，然后看是否存在值为\(i\)的数，若存在则跳过；否则找到剩下的数中第一个大于\(i\)的数让它变成\(i\)即可
排序或直接用multiset即可完成上述操作
#include<cstdio>
#include<iostream>
#include<set>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int t,n,x; long long ans; multiset <int> s;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%d",&n),s.clear(),i=1;i<=n;++i)
scanf("%d",&x),s.insert(x); for (ans=0,i=1;i<=n;++i)
{
if (s.begin()==s.end()) break;
if (x=*s.begin(),x==i)
{
while (s.begin()!=s.end()&&*s.begin()==i) s.erase(s.begin());
} else ans+=x-i,s.erase(s.begin());
}
printf("%lld\n",ans);
}
return 0;
}
D. Letter Exchange
首先排除掉那些一开始就win的人，然后考虑贪心地来匹配
对于形如wii和wnn这样一次交换可以满足两个要求的情况，我们优先匹配
而且除了以上这种，iii和nnn也可以优先交换，因为它们每次交换也是一次满足两个要求
然后处理完上面的情况后再考虑每次满足一个要求地改进即可
通过一些漂亮的写法可以使得代码非常优美简洁
#include<cstdio>
#include<iostream>
#include<map>
#include<array>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
typedef array <int,3> T;
typedef vector <int> VI;
const T tar={1,1,1};
const int N=100005;
const char ch[3]={'w','i','n'};
int t,n,tot,cnt,a1[N],a2[N]; char s[10],c1[N],c2[N]; map <T,VI> rst;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i,j; for (scanf("%d",&n),cnt=tot=0,i=1;i<=n;++i)
{
T tmp={0,0,0}; for (scanf("%s",s+1),j=1;j<=3;++j)
if (s[j]=='w') ++tmp[0]; else if (s[j]=='i') ++tmp[1]; else ++tmp[2];
if (tmp!=tar) ++tot,rst[tmp].push_back(i);
}
while (tot)
{
int mx=0; T p1,p2;
for (auto &[u1,v1]:rst) if (!v1.empty())
for (auto &[u2,v2]:rst) if (u1!=u2&&!v2.empty())
{
int cur=0; for (i=0;i<3;++i)
if (u1[i]<1&&u2[i]>1) ++cur; else if (u1[i]>1&&u2[i]<1) ++cur;
if (cur>mx) mx=cur,p1=u1,p2=u2;
}
int id1=rst[p1].back(),id2=rst[p2].back(); ++cnt;
a1[cnt]=id1; a2[cnt]=id2; rst[p1].pop_back(); rst[p2].pop_back();
for (i=0;i<3;++i) if (p2[i]>1) c2[cnt]=ch[i],--p2[i],++p1[i];
else if (p1[i]>1) c1[cnt]=ch[i],--p1[i],++p2[i];
if (p1!=tar) rst[p1].push_back(id1); else --tot;
if (p2!=tar) rst[p2].push_back(id2); else --tot;
}
for (printf("%d\n",cnt),i=1;i<=cnt;++i)
printf("%d %c %d %c\n",a1[i],c1[i],a2[i],c2[i]);
}
return 0;
}
E. Monsters (hard version)
考虑对于C题的做法，我们进行形式化的描述
先将\(a\)升序排序，以样例为例，即\(a=\{1,1,1,4,4,5\}\)，我们记\(b=\{1,1,1,2,3,4\}\)，即每个数在第几次亵渎的时候被杀死
不难发现\(ans=\sum_{i=1}^n a_i-\sum_{i=1}^n b_i\)，但是这样并不好计算答案
不妨先考虑一种特殊情况，\(b\)中没有重复元素，此时答案显然为\(\sum_{i=1}^n a_i-\frac{n(n+1)}{2}\)
那么如果\(b\)中有重复元素怎么办呢，我们可以考虑去掉其中的某些不产生贡献的元素（比如上面例子的第二个、第三个\(1\)）
稍加观察，我们发现如果\(\le i\)的数超过\(i\)个，则一定可以删去其中的某些元素使得\(b\)中的元素不相同且贡献不变
不难发现由于我们一个一个地把数添加进来，因此如果出现重复的情况，只要把删除其中最小的一个即可
具体实现的话可以令\(s_i\)表示小于等于\(i\)的数的个数，然后对于下标\(i\)初值赋值成\(-i\)
在用线段树维护区间最大值后如果存在全局最大值大于\(0\)的情况则说明要删除，在线段树上二分即可
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int t,n,x,cur; long long sum;
class Segment_Tree
{
private:
struct segment
{
int mx,tag;
}node[N<<2];
#define M(x) node[x].mx
#define T(x) node[x].tag
#define TN CI now=1,CI l=1,CI r=n
#define LS now<<1,l,mid
#define RS now<<1|1,mid+1,r
inline void apply(CI now,CI v)
{
M(now)+=v; T(now)+=v;
}
inline void pushup(CI now)
{
M(now)=max(M(now<<1),M(now<<1|1));
}
inline void pushdown(CI now)
{
if (T(now)) apply(now<<1,T(now)),apply(now<<1|1,T(now)),T(now)=0;
}
public:
inline void build(TN)
{
node[now]=(segment){(int)-1e9,0}; if (l==r) return (void)(M(now)=-l);
int mid=l+r>>1; build(LS); build(RS); pushup(now);
}
inline void modify(CI beg,CI end,CI v,TN)
{
if (beg<=l&&r<=end) return apply(now,v); int mid=l+r>>1; pushdown(now);
if (beg<=mid) modify(beg,end,v,LS); if (end>mid) modify(beg,end,v,RS); pushup(now);
}
inline int query(TN)
{
if (l==r) return l; int mid=l+r>>1; pushdown(now);
if (M(now<<1)>0) return query(LS); else return query(RS);
}
inline int rt_max(void)
{
return M(1);
}
#undef M
#undef T
#undef TN
#undef LS
#undef RS
}SEG;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i; for (scanf("%d",&n),SEG.build(),sum=cur=0,i=1;i<=n;++i)
{
scanf("%d",&x); SEG.modify(x,n,1); sum+=x; ++cur;
if (SEG.rt_max()>0) x=SEG.query(),SEG.modify(x,n,-1),sum-=x,--cur;
printf("%lld%c",sum-1LL*cur*(cur+1)/2LL," \n"[i==n]);
}
}
return 0;
}
Postscript
F数数感觉搞不动啊，先弃了弃了
标签：CODE,based,Cup,int,RI,freopen,const,include,Round From： https://www.cnblogs.com/cjjsb/p/17173324.html