| 题号 | A | B | C | D | E | F | G | H | I | J | K | L |
| 状态 | Ο | . | . | Ο | . | . | Ø | Ø | Ο | Ο | . | Ο |
Ο：当场
Ø：已补
. : 待补
A. Edit Distance
Thinking：kk pai爷
Code：kk
不能直接反转，比如"010101"，直接反转后就变成"101010"，右移一位，然后加个0就可以了。
所以要先统计01的数量，如果0大于1，就全变成1,1大于0，就全变成0（从数量上的改变就大于s/2了），相等的话，就看首位是0还是1，取相反，后面和首位不一样就行（位置）。
#include<bits/stdc++.h>
#include<tr1/unordered_map>
#include<bits/stdc++.h>
#define clr(a,b) memset(a,b,sizeof(a))
#define fpn() freopen("simple.in","r",stdin)
#define rd read()
using namespace std;
const int maxn=;
typedef long long ll;
int a,b;
char s[maxn];
int main(){
cin>>s+;
int n=strlen(s+);
for(int i=;i<=n;i++)
{
if(s[i]=='')a++;
else b++;
}
if(a>b){
for(int i=;i<=n;i++)
{
printf("");
}
puts("");
}else if(a<b){
for(int i=;i<=n;i++)
{
printf("");
}
puts("");
}else{
if(s[]==''){
printf("");
for(int i=;i<=n;i++)
{
printf("");
}
puts("");
}else{
printf("");
for(int i=;i<=n;i++)
{
printf("");
}
puts("");
}
}
}
D. Icy Land
Thinking：kk
Code：pai爷
首先我们考虑大一点的矩阵，对于$n*m$来说，中心的$（n-2）*（m-2）$的矩阵中，只要有冰地，这个冰地就必然到达不了，因为会直接划过去，所以我们要把中间这个矩阵直接变成"#"，然后我们要确保外围的过道上有一个#能让我们进入中心区域。
然后特殊考虑$2*n$的矩阵，还是中心的两行，只要上下有一个就可以了。
#include<bits/stdc++.h>
#include<tr1/unordered_map>
#include<bits/stdc++.h>
#define clr(a,b) memset(a,b,sizeof(a))
#define fpn() freopen("simple.in","r",stdin)
#define rd read()
using namespace std;
const int maxn=;
typedef long long ll;
int n,m,ans=,flag;
char s[][];
void do1()
{
for(int i=;i<=m-;i++)
if(s[][i]=='.') ans++;
}
void do2()
{
for(int i=;i<=n-;i++)
if(s[i][]=='.') ans++;
}
void do3()
{
for(int i=;i<=n-;i++)
if(s[i][]!='#'&&s[i][]!='#') ans++;
}
void do4()
{
for(int i=;i<=m-;i++)
if(s[][i]!='#'&&s[][i]!='#') ans++;
}
void do5()
{
for(int i=;i<=n-;i++)
for(int j=;j<=m-;j++)
if(s[i][j]=='.') ans++;
flag=;
for(int i=;i<=m-;i++)
if(s[][i]=='#'||s[n][i]=='#') flag=;
for(int i=;i<=n-;i++)
if(s[i][]=='#'||s[i][m]=='#') flag=;
ans+=flag;
}
void work()
{
if(n==) do1();
else if(m==) do2();
else if(m==) do3();
else if(n==) do4();
else do5();
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) scanf("%s",s[i]+);
work();
printf("%d\n",ans);
}
F. Popping Balloons
待补。 z
G. Go Make It Complete
补题：kk
题意：给了一个无向图，要求你把这个无向图变成完全图，连边的条件是这条边的两个点的当前度数和大于等于k，问能变成完全图的最大的k是多少。
思路：虽然AC了，但是感觉时间复杂度不太对。
首先我们先把需要连的边处理出来，然后发现这个k是有可以二分的性质的，所以我们就二分k，每次把度数和大于等于k的边连上，更新度数，扫一遍这两个点连接的所有需要连的边，大于等于k的塞入队列，不断重复直到队列为空。类似拓扑排序。
但是这样做的时间复杂度是$N3logn$，居然能过，，网上看到有人说可以用set维护边，但是细想感觉是不对的，所以比赛的时候，有这种看似过不了的算法，还是可以写一写的。
#include<bits/stdc++.h>
#define clr(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=;
int mp[maxn][maxn],d[maxn],a[maxn][maxn],deg[maxn];
int n,m;
struct edge{
int u,v;
}b[maxn*maxn];
int u,v,cnt;
bool judge(int k)
{
memcpy(deg,d,sizeof(deg));
memcpy(a,mp,sizeof(mp));
queue<edge>q;
for(int i=;i<=cnt;i++)
{
int u=b[i].u,v=b[i].v;
if(deg[u]+deg[v]>=k){
a[u][v]=a[v][u]=;
q.push({u,v});
}
}
while(!q.empty())
{
edge st=q.front();
q.pop();
int u=st.u,v=st.v; deg[u]++,deg[v]++;
for(int i=;i<=n;i++)
{
if(a[i][u]==&°[i]+deg[u]>=k){
q.push({i,u});
a[i][u]=a[u][i]=;
}
if(a[i][v]==&°[i]+deg[v]>=k){
q.push({i,v});
a[i][v]=a[v][i]=;
}
}
}
for(int i=;i<=n;i++)
{
if(deg[i]!=n-)return false;
}
return true;
}
int main(){
while(cin>>n>>m)
{
clr(mp,);
clr(d,);
cnt=;
for(int i=;i<=m;i++)
{
scanf("%d%d",&u,&v);
mp[u][v]=mp[v][u]=;
d[u]++,d[v]++;
}
for(int i=;i<=n;i++)
{
mp[i][i]=;
for(int j=i+;j<=n;j++)
{
if(mp[i][j]==){
b[++cnt].u=i,b[cnt].v=j;
}
}
}
int l=,r=,mid,ans;
while(l<r)
{
mid=(l+r)>>;
if(judge(mid)){
ans=mid,l=mid+;
}else{
r=mid;
}
}
printf("%d\n",ans);
}
}
H. Lexical Sign Sequence
训练的时候想的似乎是正解？不过电脑在刚J题，没时间写
补题：zz
题意：给定一个只包含-1，0，1的数列，-1和1的位置的数不能改变，0的位置必须改变成-1或者1，并且使得改变后的数列满足k个条件，这k个条件都是一段区间里的数的和要大于等于某个数，如果这样的序列不存在就输出Impossible，否则输出字典序最小的序列。
思路：可以根据初始的数列和每个给定的条件算出这k个区间每个区间最多有多少个-1（原本的-1不算），如果算出来的数量是小于0的，就肯定不存在；然后建立一个set，初始为空，根据最多能有都少个-1从小到大排序，枚举1到n位，枚举到第i位时，把不包含这个数的区间从set中删除，把起点为i的区间放到set里。如果原位子上的数为1或-1，就不动；如果set为空，这个位子上就放-1；如果set里有数，如果set里的第一个数大于0，就放-1，并且set里的数全减1，反之放1。
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<math.h>
#include<cmath>
#include<time.h>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<algorithm>
#include<numeric>
#include<stack>
#include<bitset>
#include<unordered_map>
const int maxn = 0x3f3f3f3f;
const double EI = 2.71828182845904523536028747135266249775724709369995957496696762772407663035354594571382178525166427;
const double PI = 3.141592653589793238462643383279;
//#ifdef TRUETRUE
//#define gets gets_s
//#endif
using namespace std;
int c[], sum1[], sum2[], mp[], ans[];
struct s
{
int a, b, c, d;
}z[];
struct ss
{
int a, f, d,id;
}zz[];
struct sss
{
int v, id;
bool operator < (const sss &rhs) const
{
if (v == rhs.v)
{
return id < rhs.id;
}
return v < rhs.v;
}
};
set<sss>st;
inline bool comp(ss a, ss b)
{
if (a.a == b.a)
{
return a.f > b.f;
}
return a.a < b.a;
}
int main(void)
{
//ios::sync_with_stdio(false);
int n, k, i, tmp, n1, n2, x, wz, qq, pos;
bool flag;
while (~scanf("%d %d", &n, &k))
{
sum1[] = ;
sum2[] = ;
st.clear();
memset(mp, , sizeof(mp));
for (i = ; i <= n; i++)
{
scanf("%d", c + i);
if (c[i] == )
{
sum1[i] = sum1[i - ];
sum2[i] = sum2[i - ];
}
else if (c[i] == -)
{
sum1[i] = sum1[i - ] + ;
sum2[i] = sum2[i - ];
}
else
{
sum1[i] = sum1[i - ];
sum2[i] = sum2[i - ] + ;
}
}
flag = false;
for (i = ; i < k; i++)
{
scanf("%d %d %d", &z[i].a, &z[i].b, &z[i].c);
zz[i].a = z[i].a;
zz[i].f = -;
zz[i].id = i;
zz[i + k].a = z[i].b + ;
zz[i + k].f = ;
zz[i + k].id = i;
n1 = sum1[z[i].b] - sum1[z[i].a - ];
n2 = sum2[z[i].b] - sum2[z[i].a - ];
x = z[i].c - (n2 - n1);
wz = z[i].b - z[i].a + - n1 - n2;
if (x > wz)
{
flag = true;
}
else
{
z[i].d = (wz - x) / ;
zz[i].d = z[i].d;
zz[i + k].d = z[i].d;
//printf("z[i].d = %d\n",z[i].d);
}
}
if (flag)
{
printf("Impossible\n");
continue;
}
sort(zz, zz + k * , comp);
qq = ;
pos = ;
/*for (i = 0;i < 2 * k;i++)
{
printf(" %d %d %d %d %d\n",i,zz[i].a,zz[i].id,zz[i].d,zz[i].f);
}*/
for (i = ; i <= n; i++)
{
while (pos < * k && zz[pos].a == i)
{
if (zz[pos].f == -)
{
st.insert({ zz[pos].d + qq,zz[pos].id });
mp[zz[pos].id] = zz[pos].d + qq;
}
else
{
//printf(" %d %d\n", i, st.empty());
st.erase({ mp[zz[pos].id],zz[pos].id });
//printf(" %d %d\n",i,st.empty());
}
pos++;
}
if (st.empty())
{
if (c[i] == )
{
//printf("ii = %d\n",i);
ans[i] = -;
}
else
{
//printf("iii = %d\n", i);
ans[i] = c[i];
}
}
else if (c[i] == && (*st.begin()).v - qq > )
{
//printf("i = %d\n",i);
qq++;
ans[i] = -;
}
else if (c[i] == )
{
//printf("iiiii = %d\n", i);
ans[i] = ;
}
else
{
//printf("iiii = %d\n", i);
ans[i] = c[i];
}
}
for (i = ; i <= n; i++)
{
printf("%d", ans[i]);
if (i != n)
{
printf(" ");
}
}
printf("\n");
}
return ;
}
I. Lie Detector
Thinking
Code：pai爷
签到。
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<string>
#include<map>
#include<queue>
#include<vector>
#include<stack>
#define ll long long
#define maxn 4001000
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int n,p;
char s[][];
ll read()
{
ll x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
void init()
{
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%s",s[i]);
}
void work()
{
if(s[][]=='L') p=;
else p=;
for(int i=;i<=n;i++)
if(s[i][]=='L') p=!p;
if(p==) printf("LIE\n");
else printf("TRUTH\n");
}
int main()
{
init();
work();
}
J. Future Generation
题解：用F【I】【J】.c表示 处理到第i个字符串，能获得总长度为j的最小的子串（第i个字符串的子串），
预处理q数组，每个字符串的子串。代码有点丑。
#include<bits/stdc++.h>
#include<tr1/unordered_map>
#include<bits/stdc++.h>
#define clr(a,b) memset(a,b,sizeof(a))
#define fpn() freopen("simple.in","r",stdin)
#define rd read()
using namespace std;
const int maxn=;
typedef long long ll; struct node{
char c[];
int l;
}q[][]; struct nod{
int p=;
char c[];
}f[][]; int len[],n,flag[];
char s[][],c[][]; void work(int x)
{
int l=strlen(s[x]),z=;
for(int i=;i<=(<<l)-;i++)
{
len[x]++;z=;
for(int k=;k<l;k++)
{
if((i&(<<k))!=)
{
// printf("i=%d k=%d\n",i,k);
q[x][len[x]].c[++z]=s[x][k];
}
}
q[x][len[x]].l=z;
// for(int j=1;j<=z;j++) printf("%c",q[x][len[x]].c[j]);
// printf("\n");
}
}
void init()
{
for(int i=;i<=n;i++) work(i);
}
int check(int x,int j)
{
for(int i=;i<=x;i++)
if(f[][x].c[i]>q[][j].c[i]) return ;
else if(f[][x].c[i]<q[][j].c[i]) return ;
return ;
}
void dodo()
{
for(int j=;j<=len[];j++)
{
int len1=q[][j].l;
if(f[][len1].p==)
{
f[][len1].p=;
for(int k=;k<=len1;k++) f[][len1].c[k]=q[][j].c[k];
}
else{
if(check(len1,j))
{
for(int k=;k<=len1;k++) f[][len1].c[k]=q[][j].c[k];
}
}
}
for(int i=;i<=n;i++)
for(int j=;j<=*;j++)
{
if(f[i-][j].p!=)
{
for(int i1=;i1<=;i1++)
for(int j1=;j1<=i1;j1++)
c[i1][j1]='z';
for(int i1=;i1<=;i1++) flag[i1]=;
for(int k=;k<=len[i];k++)
{
int l=q[i][k].l;
if(strncmp(&(q[i][k].c[]),&(f[i-][j].c[]), l)>)
{
if(strncmp(&(c[l][]),&(q[i][k].c[]), l)>)
{
flag[l]=;
for(int kk=;kk<=l;kk++) c[l][kk]=q[i][k].c[kk];
}
}
}
for(int pq=;pq<=;pq++)
if(flag[pq]==)
{
// printf("i=%d j=%d\n",i,j);
// for(int kk=1;kk<=pq;kk++) printf("%c",c[pq][kk]);
// printf("\n");
if(f[i][j+pq].p==)
{
for(int kk=;kk<=pq;kk++)
f[i][j+pq].c[kk]=c[pq][kk],f[i][j+pq].p=;
}
else{
if(strncmp(&(f[i][j+pq].c[]),&(c[pq][]), pq)>)
for(int kk=;kk<=pq;kk++)
f[i][j+pq].c[kk]=c[pq][kk],f[i][j+pq].p=;
} }
}
}
int ans=-;
for(int i=;i<=*;i++)
if(f[n][i].p!=) ans=i;
printf("%d\n",ans);
}
int main()
{
freopen("1.txt","r",stdin);
freopen("1.out","w",stdout);
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%s",s[i]);
init();
dodo();
}
K. Boomerangs
待补 k
L：
题意：给定一个只包含-1，0，1的数列，-1和1的位置的数不能改变，0的位置必须改变成-1或者1，并且使得改变后的数列满足k个条件，这k个条件都是一段区间里的数的和要大于等于某个数，如果这样的序列不存在就输出Impossible，否则输出字典序最小的序列。
思路：可以根据初始的数列和每个给定的条件算出这k个区间每个区间最多有多少个-1（原本的-1不算），如果算出来的数量是小于0的，就肯定不存在；然后建立一个set，初始为空，根据最多能有都少个-1从小到大排序，枚举1到n位，枚举到第i位时，把不包含这个数的区间从set中删除，把起点为i的区间放到set里。如果原位子上的数为1或-1，就不动；如果set为空，这个位子上就放-1；如果set里有数，如果set里的第一个数大于0，就放-1，并且set里的数全减1，反之放1。
#include<bits/stdc++.h>
#include<tr1/unordered_map>
#include<bits/stdc++.h>
#define clr(a,b) memset(a,b,sizeof(a))
#define fpn() freopen("simple.in","r",stdin)
#define rd read()
using namespace std;
const int maxn=;
typedef long long ll;
char c[];
long long k,len;
int v[];
inline long long f(void)
{
long long i,s = ;
for(i = ;i < len;i++)
{
if(!v[i])
{
s *= ;
if(c[i] == '')
{
s += ;
}
}
}
return s;
}
int main(){
long long i;
int ans;
while(~scanf("%lld",&k))
{
scanf("%s",c);
len = strlen(c);
memset(v,,sizeof(v));
ans = ;
while()
{
if(f() <= k)
{
break;
}
bool flag = true;
for(i = ;i < len;i++)
{
if(c[i] == '' && v[i] == )
{
v[i] = ;
flag = false;
break;
}
}
if(flag)
{
for(i = ;i < len;i++)
{
if(c[i] == '' && v[i] == )
{
v[i] = ;
break;
}
}
}
ans++;
}
printf("%d\n",ans);
}
}
总结：
kk：今天比赛中途吃了个外卖（下课食堂人太多了吧）。所以中间稍微耽搁了一下下，A题一眼想到假算法，发现wa了那么多，所以等了等，果然hack了假算法，和pai爷讨论后ac，吃外卖的时候看了d题，回来稍微画了画想到正解，pai爷写的代码。后面的题目和zz、pai爷分别讨论了两道题，一道题感觉时间复杂度不对，没写完就让电脑了，一道题和zz讨论的似乎是正解，时间不够了没写。今天主要是被代码实现能力卡住了，还有没有提早提醒队友卡题的时候看新题，本来H题应该是能做的。
pai爷：喵喵喵？口胡选手？我好菜啊？字符串的操作不会？努力！
zz：去晚了一点，写了个L，J写完以后发现搜索写崩了，还不如直接二进制枚举，H想了个贪心，没时间写了。