嘿嘿嘿，第一篇文章，感觉代码可以缩起来简直不要太爽
打个div2发挥都这么差...
平均一题fail一次，还调不出错，自闭了
又一次跳A开B，又一次B傻逼错误调不出来
罚时上天，E还傻逼了..本来这场应该很前的，最后只苟在rated的人里面50
A. Chunga-Changa
随便做就行了，因为CF似乎不可以print("%d",0);于是WA了一个样例
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
typedef long long LL; int main()
{
LL x,y,z;
scanf("%lld%lld%lld",&x,&y,&z);
if (x/z+y/z==(x+y)/z) printf("%lld 0\n",(x+y)/z);
else
{
LL t=(z-y%z)%z;
LL t1=(z-x%z)%z;
LL ans=;
printf("%lld %lld\n",(x+y)/z,min(t,t1));
}
return ;
}
B. Split a Number
显然取中间最优，但可能中间有0，那就往两边找
然后一开始有一个大于号写成小于号WA了一发，然后看了半天看不出，最后使得A和B都是30min过
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
typedef long long LL;
const int N=;
char ss[N];
int n;
int cnt;
bool tf=false;
int len,a[N];
int b[N],len1;
bool JD ()
{
if (tf==false) return true;
if (len<len1) return false;
if (len>len1) return true;
for (int u=;u<=len;u++)
{
if (a[u]<b[u]) return false;
if (a[u]>b[u]) return true;
}
return true;
}
void check (int x)
{
if (ss[x+]=='') return ;
cnt++;
len1=max(x,n-x);
memset(b,,sizeof(b));
int i=x,j=n;
for (int u=len1;u>=;u--)
{
if (i>=) b[u]=b[u]+ss[i]-'';
if (j>x) b[u]=b[u]+ss[j]-'';
i--;j--;
}
for (int u=len1;u>=;u--) b[u-]=b[u-]+b[u]/,b[u]%=;
if (b[]!=)
{
len1++;
for (int u=len1;u>=;u--) b[u]=b[u-];
}
if (JD())
{
len=len1;tf=true;
for (int u=;u<=len;u++) a[u]=b[u];
}
}
int main()
{
scanf("%d",&n);scanf("%s",ss+);
cnt=;
for (int u=n/;u>=;u--)
{
check(u);
if (cnt>=) break;
}
cnt=;
for (int u=n/;u<n;u++)
{
check(u);
if (cnt>=) break;
}
for (int u=;u<=len;u++) printf("%d",a[u]);
return ;
}
C. Flag
考虑枚举左上角，那么我们要知道的就是每个点往下多少个就不同D以及在这一段里面往右多少个就不同R
贡献就是三段R的min
前两段的D要一样，问题是第三段他只要比前两段的D大就好了
于是再倒着维护一个U，然后第三段跳到左下角查询，复杂度O(nm)
然后一个变量打错了，WA了两发
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
typedef long long LL;
const int N=;
char ss[N][N];
int n,m;
int R[N][N];
int mn[N][N];
int D[N][N];
int mn1[N][N];
int main()
{
scanf("%d%d",&n,&m);
for (int u=;u<=n;u++) scanf("%s",ss[u]+);
for (int u=n;u>=;u--)
{
for (int i=m;i>=;i--)
{
if (ss[u][i]==ss[u][i+]) R[u][i]=R[u][i+]+;
else R[u][i]=;
}
}
for (int u=;u<=n;u++)
for (int i=;i<=m;i++)
{
mn1[u][i]=R[u][i];
if (ss[u][i]==ss[u-][i]) mn1[u][i]=min(mn1[u][i],mn1[u-][i]);
}
for (int u=n;u>=;u--)
for (int i=;i<=m;i++)
{
mn[u][i]=R[u][i];
if (ss[u][i]==ss[u+][i])
{
mn[u][i]=min(mn[u][i],mn[u+][i]);
D[u][i]=D[u+][i]+;
}
else D[u][i]=;
}
int ans=;
for (int u=;u<=n;u++)
for (int i=;i<=m;i++)
{
int x1,x2,x3;
x1=u;
x2=x1+D[x1][i];
x3=x2+D[x2][i];
if (D[x1][i]!=D[x2][i]) continue;
if (D[x3][i]<D[x2][i]) continue;
x3=x3+D[x2][i]-;
if (x3>n) continue;
ans=ans+min(min(mn[x1][i],mn[x2][i]),mn1[x3][i]);
//printf("%d %d %d %d %d\n",u,i,x1,x2,x3);
}
printf("%d\n",ans);
return ;
}
D. Irrigation
模拟这个过程使得所有人一样
每一次把所有i的人变为i+1
发现要维护现在又多少人，以及第k大
开个线段树就好了
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
typedef long long LL;
const LL N=;
LL n,m,Q;
LL a[N];
struct qt
{
LL l,r;
LL c;
LL s1,s2;
}tr[N*];LL num;
void bt (LL l,LL r)
{
LL now=++num;
tr[now].l=l;tr[now].r=r;tr[now].c=;
if (l==r) return ;
LL mid=(l+r)>>;
tr[now].s1=num+;bt(l,mid);
tr[now].s2=num+;bt(mid+,r);
}
LL query (LL now,LL x)
{
if (tr[now].l==tr[now].r) return tr[now].l;
LL mid=(tr[now].l+tr[now].r)>>;
LL s1=tr[now].s1,s2=tr[now].s2;
if (tr[s1].c>=x) return query(s1,x);
else return query(s2,x-tr[s1].c);
}
void add (LL now,LL c)
{
tr[now].c++;
if (tr[now].l==tr[now].r) return ;
LL mid=(tr[now].l+tr[now].r)>>;
LL s1=tr[now].s1,s2=tr[now].s2;
if (c<=mid) add(s1,c);
else add(s2,c);
}
vector<LL> vec[N];
LL ans[N];
struct qq
{
LL x,id;
}q[N];
bool cmp (qq x,qq y) {return x.x<y.x;}
int main()
{
scanf("%lld%lld%lld",&n,&m,&Q);
for (LL u=;u<=n;u++) {LL x;scanf("%lld",&x);a[x]++;}
bt(,m);
for (LL u=;u<=m;u++) vec[a[u]].push_back(u);
for (LL u=;u<=Q;u++) {scanf("%lld",&q[u].x);q[u].x-=n;q[u].id=u;}
sort(q+,q++Q,cmp);
LL now=,now1=;//�ٰ��˶�������
for (LL u=;u<=n;u++)
{
while (now1<=Q&&now+tr[].c>=q[now1].x) {ans[q[now1].id]=query(,q[now1].x-now);now1++;}
now=now+tr[].c;
LL siz=vec[u].size();
for (LL i=;i<siz;i++) add(,vec[u][i]);
}
while (now1<=Q)
{
LL t=q[now1].x-now;
t=t%m;if (t==) t=m;
ans[q[now1].id]=t;
now1++;
}
for (LL u=;u<=Q;u++) printf("%lld\n",ans[u]);
return ;
}
E1. A Story of One Country (Easy)
打的时候有点崩，不好意思说自己写了个什么傻吊玩意了
就是暴力枚举一个能切的地方就好了，递归处理，复杂度是O(n^2)的
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
typedef long long LL;
const int N=;
const int MAX=1e9;
struct qq
{
int x1,y1,x2,y2;
qq () {}
qq (int a,int b,int c,int d) {x1=a;y1=b;x2=c;y2=d;}
};
bool cmp (qq x,qq y) {return x.x1<y.x1;}
bool cmp1 (qq x,qq y) {return x.y1<y.y1;}
int n;
bool solve (vector<qq> vec)
{
int siz=vec.size();
if (siz==) return true;
vector<qq> a,b;a.clear();b.clear();
sort(vec.begin(),vec.end(),cmp);
for (int u=siz-;u>=;u--) b.push_back(vec[u]);
int mx=;
for (int u=;u<siz;u++)
{
b.pop_back();a.push_back(vec[u]);mx=max(mx,a[u].x2);
if (u!=siz-&&mx<=vec[u+].x1)
{
//printf("%d %d\n",siz,u);
return solve(a)&solve(b);
}
}
sort(vec.begin(),vec.end(),cmp1);
a.clear();b.clear();
for (int u=siz-;u>=;u--) b.push_back(vec[u]);
mx=;
for (int u=;u<siz;u++)
{
b.pop_back();a.push_back(vec[u]);mx=max(mx,a[u].y2);
if (u!=siz-&&mx<=vec[u+].y1) return solve(a)&solve(b);
}
return false;
}
int main()
{
scanf("%d",&n);
vector<qq> vec;
for (int u=;u<=n;u++)
{
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
vec.push_back(qq(a,b,c,d));
}
if (solve(vec)) printf("YES\n");
else printf("NO\n");
return ;
}
E2. A Story of One Country (Hard)
考虑优化上面这个过程，其实只需要四个方向一起枚举就可以了
枚举到最小的一个就递归下去，复杂度是启发式分裂，也就是和启发式合并一样的复杂度nlogn
但是实现有点小技巧，因为你不可以扫全部元素，否则复杂度就退化了
那么就是要维护一个有序序列，还要支持删除，显然维护4个set就行了
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<set>
using namespace std;
typedef long long LL;
const int MAX=1e9;
struct qq
{
int x1,y1,x2,y2;
qq () {}
qq (int a,int b,int c,int d) {x1=a;y1=b;x2=c;y2=d;}
};
struct cmp1
{
inline bool operator () (qq a,qq b) {return a.x1==b.x1?a.y1<b.y1:a.x1<b.x1;}
};
struct cmp2
{
inline bool operator () (qq a,qq b) {return a.y1==b.y1?a.x1<b.x1:a.y1<b.y1;}
};
struct cmp3
{
inline bool operator () (qq a,qq b) {return a.x2==b.x2?a.y2<b.y2:a.x2>b.x2;}
};
struct cmp4
{
inline bool operator () (qq a,qq b) {return a.y2==b.y2?a.x2<b.x2:a.y2>b.y2;}
};
int n;
bool solve (set<qq,cmp1> &s1,set<qq,cmp2> &s2,set<qq,cmp3> &s3,set<qq,cmp4> &s4)
{
int siz=s1.size();
if (siz==)
{
s1.clear();s2.clear();s3.clear();s4.clear();
return true;
} set<qq,cmp1> g1;g1.clear();set<qq,cmp1> :: iterator it1=s1.begin();
set<qq,cmp2> g2;g2.clear();set<qq,cmp2> :: iterator it2=s2.begin();
set<qq,cmp3> g3;g3.clear();set<qq,cmp3> :: iterator it3=s3.begin();
set<qq,cmp4> g4;g4.clear();set<qq,cmp4> :: iterator it4=s4.begin(); int mxx=,mxy=,mnx=MAX,mny=MAX;
for (int u=;u<siz-;u++)
{
mxx=max(mxx,(*it1).x2);it1++;
if (mxx<=(*it1).x1)
{
set<qq,cmp1> :: iterator now=s1.begin();
while (now!=it1)
{
qq xx=(*now);now++;
s1.erase(xx);g1.insert(xx);
s2.erase(xx);g2.insert(xx);
s3.erase(xx);g3.insert(xx);
s4.erase(xx);g4.insert(xx);
}
return solve(g1,g2,g3,g4)&solve(s1,s2,s3,s4);
}
mxy=max(mxy,(*it2).y2);it2++; if (mxy<=(*it2).y1)
{
set<qq,cmp2> :: iterator now=s2.begin();
while (now!=it2)
{
qq xx=(*now);now++;
s1.erase(xx);g1.insert(xx);
s2.erase(xx);g2.insert(xx);
s3.erase(xx);g3.insert(xx);
s4.erase(xx);g4.insert(xx);
}
return solve(g1,g2,g3,g4)&solve(s1,s2,s3,s4);
}
mnx=min(mnx,(*it3).x1);it3++;
if (mnx>=(*it3).x2)
{
set<qq,cmp3> :: iterator now=s3.begin();
while (now!=it3)
{
qq xx=(*now);now++;
s1.erase(xx);g1.insert(xx);
s2.erase(xx);g2.insert(xx);
s3.erase(xx);g3.insert(xx);
s4.erase(xx);g4.insert(xx);
}
return solve(g1,g2,g3,g4)&solve(s1,s2,s3,s4);
}
mny=min(mny,(*it4).y1);it4++;
if (mny>=(*it4).y2)
{
set<qq,cmp4> :: iterator now=s4.begin();
while (now!=it4)
{
qq xx=(*now);now++;
s1.erase(xx);g1.insert(xx);
s2.erase(xx);g2.insert(xx);
s3.erase(xx);g3.insert(xx);
s4.erase(xx);g4.insert(xx);
}
return solve(g1,g2,g3,g4)&solve(s1,s2,s3,s4);
}
}
return false;
}
int main()
{
scanf("%d",&n);
set<qq,cmp1> s1;
set<qq,cmp2> s2;
set<qq,cmp3> s3;
set<qq,cmp4> s4;
for (int u=;u<=n;u++)
{
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
s1.insert(qq(a,b,c,d));
s2.insert(qq(a,b,c,d));
s3.insert(qq(a,b,c,d));
s4.insert(qq(a,b,c,d));
}
if (solve(s1,s2,s3,s4)) printf("YES\n");
else printf("NO\n");
return ;
}