好久没写blog&&比赛题解了，最近补一下
这次还是很狗的，T3想了很久最后竟然连并查集都忘写了，然后T2map莫名爆炸。
Rating爆减。。。。。。链接不解释
好了我们开始看题。
A. 「THUPC 2017」玩游戏
看到这个题目是不是超级害怕蒟蒻看到THUPC瑟瑟发抖
然后我们仔细读一遍题，发现签到题get！
我们首先判断\(a+b\)是否可以表示为\(\sum_{i=1}^k i\)的形式
如果可以，我们就可以不断从\(k\)开始，如果\(a>=k\)那么就\(a-=k\)。这样可以保证正确性。
由于\(k=\sqrt{a+b}\)，因此不会超时也不需要任何优化。
CODE
#include<cstdio>
using namespace std;
long long a,b,tot,cnt,ans[100005],num;
int main()
{
register long long i; scanf("%lld%lld",&a,&b);
for (i=1;;++i)
{
if ((tot+=i)==a+b) { num=i; break; }
if (tot>a+b) { printf("No"); return 0; }
}
for (i=num;i>=1;--i)
{
if (a>=i) a-=i,ans[++cnt]=i;
if (!a) break;
}
for (printf("%d ",num),i=cnt;i>1;--i)
printf("%d ",ans[i]); printf("%d",ans[1]);
return 0;
}
B. 「NOIP2017模拟赛11.02」Cover
一道非常玄学的好题，在CJJ dalao的不断教导下终于会了。
我们首先先把所有操作离线读进来，按修改的数来排序，如果相同就按序号排序。
然后我们发现所有数值一样的数就被排到一起去了。
接下来我们对于所有相同的数，修改时直接区间修改打个标记即可。
然后查找时只需要查找某个位置上最早被打上标记的时间即可。
看一下数据范围，发现不卡常(良心题)，直接上线段树就艹过去了。
其实正解是\(O(n)\)的栈乱搞，但是我不会啊。
CODE
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=200005;
struct ques
{
int opt,x,y,z,id,ans;
}q[N];
struct segtree
{
int x,mark;
}tree[N<<2];
int n,m,h[N];
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
x=0; char ch=tc();
while (ch<'0'||ch>'9') ch=tc();
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc();
}
inline void write(int x)
{
if (x<0) putchar('-'),x=-x;
if (x>9) write(x/10);
putchar(x%10+'0');
}
inline bool comp1(ques a,ques b)
{
if (a.z<b.z) return 1;
if (a.z>b.z) return 0;
return a.id<b.id;
}
inline bool comp2(ques a,ques b)
{
return a.id<b.id;
}
inline void down(int rt,int x)
{
if (tree[rt].mark)
{
if (q[h[tree[rt<<1].x]].z!=x) tree[rt<<1].x=tree[rt<<1].mark=tree[rt].mark;
if (q[h[tree[rt<<1|1].x]].z!=x) tree[rt<<1|1].x=tree[rt<<1|1].mark=tree[rt].mark;
tree[rt].mark=0;
}
}
inline void modify(int rt,int l,int r,int beg,int end,int id,int x)
{
if (l!=r) down(rt,x);
if (l>=beg&&r<=end) { tree[rt].mark=id; if (q[h[tree[rt].x]].z!=x) tree[rt].x=id; return; }
int mid=l+r>>1;
if (beg<=mid) modify(rt<<1,l,mid,beg,end,id,x);
if (end>mid) modify(rt<<1|1,mid+1,r,beg,end,id,x);
}
inline int query(int rt,int l,int r,int id,int x)
{
if (l==r) return tree[rt].x?tree[rt].x:-1;
int mid=l+r>>1; if (l!=r) down(rt,x);
if (id<=mid) return query(rt<<1,l,mid,id,x); else return query(rt<<1|1,mid+1,r,id,x);
}
inline void solve(int l,int r)
{
int t=q[l].z;
for (register int i=l;i<=r;++i)
if (q[i].opt) q[i].ans=query(1,1,n,q[i].x,t); else modify(1,1,n,q[i].x,q[i].y,q[i].id,t);
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
register int i; read(n); read(m);
for (i=1;i<=m;++i)
{
read(q[i].opt); q[i].id=i;
if (q[i].opt) read(q[i].x),read(q[i].z); else read(q[i].x),read(q[i].y),read(q[i].z);
}
sort(q+1,q+m+1,comp1);
for (i=1;i<=m;++i)
h[q[i].id]=i; int l,r=0; q[m+1].z=-1;
while (r<m)
{
l=++r; while (q[l].z==q[r+1].z) ++r;
solve(l,r);
}
sort(q+1,q+m+1,comp2);
for (i=1;i<=m;++i)
if (q[i].opt)
{
if (q[i].ans!=-1) write(q[q[i].ans].z!=q[i].z?-1:q[i].ans),putchar('\n');
else puts("-1");
}
return 0;
}
C. 「NOIP2017模拟赛11.02」统计岔道口
这道题是真的狗。让我怀疑人生。
由于我很菜，所以到现在都只会推平行的情况。
首先我们考虑只有平行时，那么最小值一定是\(0\)
这个很好理解吧，令它们全部平行即可。
那么最大值就是让第\(i\)条直线与之前的\(i-1\)条直线都相交。那么在没有任何限制的情况下，\(ans=\sum_{i=1}^{n-1}\)
然后考虑加入两条直线平行的操作时，我们直接把\(ans\)减去\(num[x]\cdot num[y]\)即可。其中\(num[x]\)表示与\(x\)平行的直线的数量（自己也算）
这样我们维护并查集即可。这里由于\(n\)的范围太大，所以map大法好。
30ptsCODE
#include<cstdio>
#include<map>
using namespace std;
map <int,int> num,father;
int n,m,opt,x,y;
long long ans;
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
x=0; char ch=tc();
while (ch<'0'||ch>'9') ch=tc();
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc();
}
inline void write(long long x)
{
if (x>9) write(x/10);
putchar(x%10+'0');
}
inline int getfather(int k)
{
return father[k]==k?k:father[k]=getfather(father[k]);
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
read(n); read(m); ans=(long long)n*(n-1)/2;
while (m--)
{
read(opt); read(x); read(y);
if (!opt)
{
if (!father[x]) father[x]=x,num[x]=1;
if (!father[y]) father[y]=y,num[y]=1;
int fx=getfather(x),fy=getfather(y);
if (fx!=fy) father[fx]=fy,ans-=(long long)num[fx]*num[fy],num[fy]+=num[fx];
write(ans); puts(" 0");
}
}
return 0;
}