烤漆结束恢复训练啦!
比赛地址
Rank: 8/341
Pro: 8/9/13
[A] Algorithm Teaching
题意&题解
Dilworth定理裸题,下一篇文章中会详细讲.
代码(补)
普通的Sap居然被卡常了,必须用带当前弧优化的Sap才能过去
#pragma GCC optimize(3)
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<bitset>
#define IL inline
#define reg register
#define LL long long
#define N 110
#define NM 500010
#define INF 0x3f3f3f3f
using namespace std;
int n,m,i,j,k,tot,sum,cnt=1,lsum=1,Found,al,flow;
int a[N][N],head[NM],id[N*N],up[NM],down[NM];
int gaps[NM],gap[NM],cur[NM];
string c;
bitset <1010> v[2020];
map <string,int> M,P;
struct Flow{
int t,next,fl,re;
}e[NM*8];
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL void FAST_IO() {ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);}
IL void Add(int s,int t,int fl){
e[lsum].t=t; e[lsum].fl=fl; e[lsum].next=head[s]; e[lsum].re=lsum+1; head[s]=lsum++;
e[lsum].t=s; e[lsum].fl=0; e[lsum].next=head[t]; e[lsum].re=lsum-1; head[t]=lsum++;
}
IL int Get_ID(int x,int p){
if (!p && up[x]) return up[x];
if (p && down[x]) return down[x];
if (!p){
up[x]=x+1; cnt++; return x+1;
} else {
down[x]=x+1+200000; cnt++; return down[x];
}
}
inline void Sap(int x){
int F=al,i=0,mingap=cnt-1;
if (x==cnt) {Found=1; flow+=al; return;}
for (i=cur[x];i;i=e[i].next)
if (e[i].fl){
if (gap[e[i].t]+1==gap[x]){
al=Min(al,e[i].fl); Sap(e[i].t);
if (gap[1]>=cnt) return;
if (Found) {cur[x]=i; goto END;}
al=F;
}
mingap=Min(mingap,gap[e[i].t]);
}
for (i=head[x];i!=cur[x];i=e[i].next)
if (e[i].fl){
if (gap[e[i].t]+1==gap[x]){
al=Min(al,e[i].fl); Sap(e[i].t);
if (gap[1]>=cnt) return;
if (Found) {cur[x]=i; break;}
al=F;
}
mingap=Min(mingap,gap[e[i].t]);
}
END:
if (!Found){
gaps[gap[x]]--; if (!gaps[gap[x]]) gap[1]=cnt;
gaps[gap[x]=mingap+1]++; cur[x]=head[x];
} else e[i].fl-=al,e[e[i].re].fl+=al;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
FAST_IO();
cin>>n;
for (i=1;i<=n;i++){
cin>>m;
for (j=1;j<=m;j++){
cin>>c;
if (M[c]) a[i][j]=M[c];
else
a[i][j]=M[c]=++tot;
}
for (j=1;j<(1<<m);j++){
v[j].reset();
for (k=0;k<m;k++)
if (j&(1<<k)) v[j][a[i][k+1]]=1;
c=v[j].to_string();
if (P[c]) id[j]=P[c];
else id[j]=P[c]=++sum;
}
for (j=1;j<(1<<m);j++)
for (k=0;k<m;k++)
if (j&(1<<k))
Add(Get_ID(id[j],0),Get_ID(id[j^(1<<k)],1),1);
}
cnt++;
for (i=1;i<=sum;i++) Add(1,up[i],1),Add(down[i],cnt,1);
gaps[0]=cnt;
while (gap[1]<cnt){
Found=0; al=INF; Sap(1);
}
cout<<sum-flow<<endl;
return 0;
}
[D] Dazzling Stars
题意
在一个坐标系上有n个星星,每个星星有一个坐标和亮度.现在要求旋转这个坐标系,使得旋转后按y坐标从大到小排序得到的星星序列,也是亮度从大到小排序的序列.
求是否有合法的旋转方案.
题解
如果一个星星比另一个星星亮,但是却在它下面的话,就需要旋转坐标系.旋转时会有一个合法的旋转区间.把所有的旋转区间取交集判断是否为空即为是否有合法方案.
可进一步转化为叉积处理.
代码
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#define IL inline
#define LL long long
#define ULL unsigned LL
#define GC getchar()
#define PC putchar
#define _Q_(x) {register char _c=GC,_v=1;for(x=0;_c<48||_c>57;_c=GC)if(_c==45)_v=-1;
#define _H_(x) for(;_c>=48&&_c<=57;x=(x<<1)+(x<<3)+_c-48,_c=GC);if(_v==-1)x=-x;}
#define sc(x) _Q_(x)_H_(x)
#define se(x) _Q_(x)else if(_c==EOF)return 0;_H_(x)
template<class T>
void UPRT(const T _){if(_>=10)UPRT(_/10);PC(_%10+48);}
#define UPL(_) UPRT(_),PC(10)
template<class T>
void PRT(const T _){if(_<0){PC(45),UPRT<ULL>(-(ULL)_);return;}if(_>=10)PRT(_/10);PC(_%10+48);}
#define PL(_) PRT(_),PC(10)
constexpr int MN(1e5);
IL int sign(LL x)
{
return x < 0 ? -1 : (x > 0 ? 1 : 0);
}
struct Po
{
LL x, y;
Po() {}
Po(LL x, LL y) : x(x), y(y) {}
Po operator +(const Po &o) const {return Po(x+o.x, y+o.y);}
Po operator -(const Po &o) const {return Po(x-o.x, y-o.y);}
LL operator *(const Po &o) const {return x*o.x + y*o.y;}
LL operator ^(const Po &o) const {return x*o.y - y*o.x;}
bool operator <(const Po & o) const
{
if (x * o.x < 0)
return x < o.x;
if (!sign(x) && !sign(o.x))
return y < o.y;
if (!sign(x))
return sign(y) <= 0 ? x < o.x : false;
if (!sign(o.x))
return sign(o.y) <= 0 ? x < o.x : true;
return y * o.x < o.y * x;
}
} a[MN];
LL b[MN];
std::vector<Po> v;
int main()
{
int n; sc(n)
if (n == 3)
return puts("Y"), 0;
for (int i = 0; i < n; i ++)
{
sc(a[i].x)
sc(a[i].y)
sc(b[i])
}
for (int i = 0; i < n; i ++)
for (int j = 0; j < n; j ++)
if (b[i] > b[j])
v.emplace_back(a[j] - a[i]);
if (v.size() < 3)
return puts("Y"), 0;
std::sort(v.begin(), v.end());
bool ok = false;
for (int i=0, sz=v.size(); i<sz && not ok; ++i)
{
int ii = i+1;
if (ii == sz)
ii = 0;
if (((v[i] ^ v[ii]) == 0 && (v[i] * v[ii]) < 0) || (v[i] ^ v[ii]) < 0)
ok = true;
}
puts(ok ? "Y" : "N");
return 0;
}
[E] Eggfruit Cake
题意&题解
签到题
代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
char s[200005];
int k;
long long int ans;
int main() {
scanf("%s%d", s, &k);
int n = strlen(s);
for (int i = n; i < n+n; i++) s[i] = s[i-n];
int up = 999999;
for (int i = n+n; i >= 0; i--) {
if (s[i] == 'E') up = i;
if (i < n) ans += max(0, k-(up-i+1)+1);
}
cout << ans << endl;
}
[F] Fabricating Sculptures
题意
给出n块正方形积木,要求搭出底座长度为l块积木的一座塔.塔的高度不限,要求每一层的长度必须大于等于上面一层.求有多少种合适的搭法.
题解
f[pre][rest]表示上一层的长度为pre,目前还剩下rest块积木时,所能搭出的塔的种类数.考虑如下转移过程:
f[pre][rest]=\sum f[i][rest-i]*(pre-i+1)
也就是枚举下一层的高度,算出方案数后再乘以长度之差,就是对当前状态的贡献.此时一共有n^2个状态,但是状态的转移过程要比n^2大很多.所以考虑计算贡献,用f[i][rest-i]试着去更新f[pre][rest].中间需要用一个前缀和来维护.
这样时间复杂度就降到了O(n^2)
代码
#pragma GCC optimize(3)
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define IL inline
#define reg register
#define LL long long
#define N 5010
#define INF 0x3f3f3f3f
using namespace std;
int l,s,i;
LL M[N][N],a[N][N];
const int MOD=1000000007;
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL LL Min(LL a,LL b){return (a<b)?a:b;}
IL LL Max(LL a,LL b){return (a>b)?a:b;}
IL LL read(){
LL p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
IL void Work(){
reg int i=0,j=0;
LL x=0,t=0;
for (i=1;i<=5000;i++) M[0][i]=1;
for (i=1;i<=5000;i++) M[1][i]=i;
for (i=1;i<5000;i++)
a[1+i][i]=(a[1+i][i]+M[1][i])%MOD;
for (i=1;i<=5000;i++)
a[i][i]=(a[i][i]+1)%MOD;
for (i=2;i<=5000;i++){
x=t=0;
for (j=1;j<=5000;j++){
t=(t+a[i][j])%MOD; x=(x+t)%MOD; M[i][j]=x;
if (i+j<5000){
a[i+j][j]=(a[i+j][j]+M[i][j])%MOD;
}
}
}
cout<<M[s-l][l]<<endl;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
l=read(); s=read();
if (l==s){
cout<<"1"<<endl;
return 0;
}
if (s<l){
cout<<"0"<<endl;
return 0;
}
memset(M,0,sizeof(M));
memset(a,0,sizeof(a));
Work();
return 0;
}
[G] Gluing Pictures
题意
给出一个母串,然后有一堆询问.每一次询问会给出一个字符串,问最少从母串中取出几段子串,可以拼出给出的字符串.(取出的子串可以有重叠部分,也就是可以理解为是一次一次取的,用完会放回去).
题解
贪心,尽可能多地取子串.在后缀数组上二分即可.
代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 400005;
char ch[MAXN], All[MAXN], str[MAXN];
int SA[MAXN], srank[MAXN], Height[MAXN], tax[MAXN], tp[MAXN], a[MAXN], n, m;
int k, pl[MAXN], len[MAXN], yuan[MAXN], zuo[MAXN], you[MAXN];
void RSort() {
for (int i = 0; i <= m; i++) tax[i] = 0;
for (int i = 1; i <= n; i++) tax[srank[tp[i]]]++;
for (int i = 1; i <= m; i++) tax[i] += tax[i-1];
for (int i = n; i >= 1; i--) SA[tax[srank[tp[i]]]--] = tp[i];
}
int cmp(int *f, int x, int y, int w) {
return f[x]==f[y] && f[x+w]==f[y+w];
}
void Suffix() {
for (int i = 1; i <= n; i++) srank[i] = a[i], tp[i] = i;
m = 127, RSort();
for (int w = 1, p = 1, i; p < n; w += w, m = p) {
for (p = 0, i = n-w+1; i <= n; i++) tp[++p] = i;
for (i = 1; i <= n; i++) if (SA[i] > w) tp[++p] = SA[i] - w;
RSort(), swap(srank, tp), srank[SA[1]] = p = 1;
for (i = 2; i <= n; i++) srank[SA[i]] = cmp(tp, SA[i], SA[i-1], w) ? p : ++p;
}
int j, k = 0;
for (int i = 1; i <= n; Height[srank[i++]] = k)
for (k = k ? k-1 : k, j = SA[srank[i]-1]; a[i+k]==a[j+k]; ++k);
}
int find(int st, int up) {
/*for (int i = st; i < st+up; i++) printf("%c", a[i]); printf(" ");
if (zuo[srank[st]] == -1) printf("--");
else for(int i = zuo[srank[st]]; i <= len[0]; i++) printf("%c", a[i]);
cout << " ";
if (you[srank[st]] == -1) printf("--");
else for(int i = you[srank[st]]; i <= len[0]; i++) printf("%c", a[i]);
cout << endl;*/
int ans1 = 0, ans2 = 0;
//printf("%d %d\n", up, len[0]-zuo[srank[st]]);
for (int i = 0; i <= min(up, len[0]); i++) {
if (a[st+i] != a[zuo[srank[st]]+i]) break;
ans1 = i+1;
}
for (int i = 0; i <= min(up, len[0]); i++) {
if (a[st+i] != a[you[srank[st]]+i]) break;
ans2 = i+1;
}
ans1 = min(ans1, len[0]);
ans2 = min(ans2, len[0]);
//cout << ans1 << " " << ans2 << endl;
return max(ans1, ans2);
}
int main() {
scanf("%s%d", str, &k);
n = strlen(str);
len[0] = n;
for (int i = 0; i < n; i++) a[i+1] = str[i];
for (int i = 1; i <= k; i++) {
scanf("%s", str);
len[i] = strlen(str); pl[i] = n;
for (int j = 0; j < len[i]; j++) a[n+j+1] = str[j];
n += len[i];
}
Suffix();
for (int i = 1; i <= n; i++) yuan[i] = -1;
for (int i = 1; i <= len[0]; i++) yuan[srank[i]] = i;
int p = -1;
for (int i = 1; i <= n; i++) {
if (yuan[i] != -1) p = yuan[i];
zuo[i] = p;
}
p = -1;
for (int i = n; i >= 1; i--) {
if (yuan[i] != -1) p = yuan[i];
you[i] = p;
}
/*
for (int i = 1; i <= n; i++) printf("%c", a[i]);
cout << endl;
for (int i = 1; i <= n; i++) printf("%2d ", srank[i]);
cout << endl;
for (int i = 1; i <= n; i++) printf("%2d ", yuan[i]);
cout << endl;
for (int i = 1; i <= n; i++) printf("%2d ", zuo[srank[i]]);
cout << endl;
for (int i = 1; i <= n; i++) printf("%2d ", you[srank[i]]);
cout << endl;
*/
for (int i = 1; i <= k; i++) {
int plen = 0;
int flag = 1;
int ans = 0;
while(plen < len[i]) {
//printf("%d %d\n", pl[i], plen);
int now = find(pl[i]+plen+1, len[i]-plen);
//return 0;
if (now == 0) { flag = 0; break; }
plen += now;
/*for (int j = pl[i]+plen; j <= pl[i]+len[i]; j++) printf("%c", a[j+1]);
cout << " ";
for (int j = pl[i]+plen; j <= pl[i]+plen+now; j++) printf("%c", a[j+1]);
cout << endl;*/
ans++;
}
if (flag) printf("%d\n", ans);
else printf("-1\n");
}
return 0;
}
[I] Improve SPAM
题意&题解
拓扑排序,签到题
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<queue>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL long long
#define N 2010
#define MOD 1000000007
#define INF 0x3f3f3f3f
using namespace std;
int n,m,i,j,k,x,y,lsum=1,cnt;
LL Ans;
LL t[N];
int head[N],v[N],f[N],d[N];
struct Edge{
int t,next,l;
}e[N*N*4];
queue <int> Q;
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
inline void Add(int s,int t){
e[lsum].t=t; e[lsum].next=head[s]; head[s]=lsum++;
}
IL void Dfs(int x){
int i=0;
v[x]=1;
for (i=head[x];i;i=e[i].next)
if (!v[e[i].t]) Dfs(e[i].t);
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
n=read(); m=read();
for (i=1;i<=m;i++){
k=read();
for (j=1;j<=k;j++){
x=read(); Add(i,x); d[x]++;
}
}
Dfs(1);
for (i=1;i<=n;i++)
if (!v[i])
for (j=head[i];j;j=e[j].next)
d[e[j].t]--;
memset(v,0,sizeof(v));
t[1]=1; Ans=0; Q.push(1);
while (!Q.empty()){
x=Q.front(); Q.pop();
for (i=head[x];i;i=e[i].next){
d[e[i].t]--; t[e[i].t]=(t[e[i].t]+t[x])%MOD;
if (e[i].t>m){
v[e[i].t]=1;
continue;
}
if (d[e[i].t]==0) Q.push(e[i].t);
}
}
for (i=1;i<=n;i++) if (v[i]) Ans=(Ans+t[i])%MOD,cnt++;
cout<<Ans<<" "<<cnt<<endl;
return 0;
}
[K] Know your Aliens
题意
给出某个多项式函数在2k这些位置的正负号情况,且已知这个多项式只有整数根.求这个多项式.
题解
正负号出现变化的时候,中间位置就是根.数据保证了系数不超过long long,所以直接暴力算就行了.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL long long
#define N 20010
#define INF 0x3f3f3f3f
using namespace std;
int n,i;
LL x,y;
LL f[N],g[N],h[N];
char c[N];
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
IL void Mul(LL p){
int i=0;
for (i=0;i<=n;i++) h[i]=f[i]*(-p);
for (i=n+1;i;i--) f[i]=f[i-1]; f[0]=0;
n++;
for (i=n-1;i>=0;i--) f[i]+=h[i];
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
scanf("%s",&c);
n=0; f[0]=1; x=2;
for (i=1;i<strlen(c);i++){
if (c[i]==c[i-1]){
x+=2; continue;
}
Mul(x+1); x+=2;
}
if (c[strlen(c)-1]=='A') x=-1;
else x=1;
cout<<n<<endl;
for (i=n;i>=0;i--)
cout<<f[i]*x<<" ";
return 0;
}
[L] Leverage MDT
题意
给出一个黑白矩形,可以选择某一行,将这一行的颜色翻转.可以任意多次执行翻转操作.求操作过后,能够取出的最大同色子方阵的面积.
题解
先不考虑翻转操作,那么取出的方阵一定满足同一行的颜色都相同,不同行则不一定.所以直接在dp求最大黑白子矩形的板子上改一下判断条件即可.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define IL inline
#define reg register
#define LL long long
#define N 1010
#define INF 0x3f3f3f3f
using namespace std;
int i,j,k,n,m,Ans,x,y;
char c[N];
int l[N][N],r[N][N],h[N][N],a[N][N],f[N][N];
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++){
scanf("%s",&c);
for (j=1;j<=m;j++)
a[i][j]=(c[j-1]=='G')?1:0;
}
for (i=1;i<=n;i++) f[i][m]=1;
for (i=1;i<=m;i++) f[n][i]=1;
Ans=1;
for (i=n-1;i>=1;i--)
for (j=m-1;j>=1;j--)
if (a[i][j]==a[i][j+1]&&a[i+1][j]==a[i+1][j+1]){
f[i][j]=Min(f[i][j+1],Min(f[i+1][j],f[i+1][j+1]))+1;
Ans=Max(Ans,f[i][j]);
} else f[i][j]=1;
printf("%d\n",Ans*Ans);
return 0;
}
[M] Mountain Ranges
题意&题解
签到题
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL long long
#define N 1010
#define INF 0x3f3f3f3f
using namespace std;
int n,x,i,Ans,y,j;
int a[N];
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
n=read(); x=read();
for (i=1;i<=n;i++) a[i]=read();
Ans=1; i=1;
while (i<n){
for (j=i+1;j<=n;j++)
if (a[j]-a[j-1]>x) {
j--; break;
}
if (j>n) j--;
Ans=Max(Ans,j-i+1);
i=j+1;
}
cout<<Ans<<endl;
return 0;
}
总结
烤漆结束后的第一次训练.
前期手感明显感觉生疏了一些,一些签到题上多吃了很多次罚时.英文题面太长导致开题的速度有些慢,这一点需要锻炼.中期多线程写F和G的时候有些慢,导致最后位于8题罚时垫底的位置.
整体的发挥尚可,如果可以面对面交流的话效率肯定会更高.以后要着重练一下中档题的推导过程.
声明:
本文采用
BY-NC-SA
协议进行授权，如无注明均为原创，转载请注明转自
Marvolo
本文地址: 2019-2020 ACM-ICPC Latin American Regional Programming Contest部分题解
本文地址: 2019-2020 ACM-ICPC Latin American Regional Programming Contest部分题解
