Codeforces Round #764 (Div. 3)
E Masha-forgetful
题意：
给你N串长度为M的已知字符串，最后给你一个字符串S，该字符串S需要由以上N种字符串的子串构成而来，但是子串的长度需要 >= 2。
如果能够构成，那么请输出各个字符串所使用的的范围(L左边界 , R右边界 , idx所用字符串编号)。
否则输出-1表示不能构成。
（一个子串可以重复用。
思路：
①要求长度 >= 2，我们可以想到，其实只需要取出所有字符串的子串长度为 2 or 3 看看是否是S的序列即可，是的话，打一个标记
②我们已经得到了字符串S各个位置上是否有相应的长度为2 or 3的子串来构成它
有点啰嗦，我们来看个例子：
4 7
7968636
9486033
4614224
5454197
9482268下面的是字符串S，上面的是用于构成它的
第一步，看看长度为2的子串是否在前N个字符串中可以寻找到
94：第二个字符串中可以找到 保存下来下标 2 1，代表第二个字符串的第一个位置有一个长度为2的子串可以匹配
48：2 2
82：无
22：3 5
26：无
68：1 3
这样长度为2的所有能够匹配就找完了
第二步，看看长度为3的子串是否可以在前N个字符串中找到
948：2 1
482：无
822：无
226：无
268：无
这样所有可以构成的信息就找完啦
最后跑一遍DP将上面找到的零散信息整合起来，看看是否可以构成字符串S即可。
当然我们需要保存状态的上一个状态从哪里转移过来的，用于输出答案。
状态转移方程在这简单提醒一下：DP[i]表示S字符串中[0 , i]是否可以由以上信息构成 遍历i的同时检查一下第i个位置是否有我们之前搜集的信息，有的话，可以从i - 2 or i - 3转移 当然，在最后，如果DP[n] = 1的话，那么可以构成字符串S，也就是有解~查看代码
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 1e3 + 7;
char s[MAXN],a[MAXN][MAXN];
int dp[MAXN],pre[MAXN],len[MAXN];
int id[2][MAXN][2];
int s1[MAXN],top = 0,s2[MAXN];
/*
1
4 7
7968636
9486033
4614224
5454197
9482268
1
1 15
123645678239143
123456789123456
*/
//0 -> 长度2 1 -> 长度3 0 -> 第几个字符串 1 -> 该字符串的位置
void solve()
{
int n,m;
scanf("%d %d",&n,&m);
for(int i = 1;i <= n;++i) scanf(" %s",a[i] + 1);
scanf(" %s",s + 1);
memset(id,0,sizeof id);
for(int i = 1;i < m;++i)
{
int flag = 0;
for(int j = 1;j <= n;++j)
{
for(int k = 1;k < m;++k)
if(s[i] == a[j][k] && s[i + 1] == a[j][k + 1])
{
flag = 1;
id[0][i][0] = j;
id[0][i][1] = k;
break;
}
if(flag) break;
}
}
for(int i = 1;i < m - 1;++i)
{
int flag = 0;
for(int j = 1;j <= n;++j)
{
for(int k = 1;k < m - 1;++k)
if(s[i] == a[j][k] && s[i + 1] == a[j][k + 1] && s[i + 2] == a[j][k + 2])
{
flag = 1;
id[1][i][0] = j;
id[1][i][1] = k;
break;
}
if(flag) break;
}
}
memset(dp,0,sizeof dp);
memset(pre,-1,sizeof pre);
memset(len,-1,sizeof len);
dp[0] = 1;
for(int i = 2;i <= m;++i)
{
if(id[0][i - 1][0])
dp[i] |= dp[i - 2],pre[i] = i - 2,len[i] = 0;
if(i >= 3 && !dp[i] && id[1][i - 2][0])
dp[i] |= dp[i - 3],pre[i] = i - 3,len[i] = 1;
}
if(!dp[m])
{
puts("-1");
return ;
}
top = 0;
int now = m;
while(now != -1)
{
s1[++top] = now;
s2[top] = len[now];
now = pre[now];
}
printf("%d\n",top - 1);
now = m;
for(int i = top - 1;i >= 1;--i)
{
int c = pre[s1[i]] + 1,k = s2[i];
int l = (k & 1 ? 3 : 2);
printf("%d %d %d\n",id[k][c][1],id[k][c][1] + l - 1,id[k][c][0]);
}
return ;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
solve();
return 0;
}题意：
给你一个数N，需要你猜一个一开始范围在N以内的数X，每次你可以做以下操作：
+ c(c ∈ [1,n - 1])，然后裁判程序会返回给你 (x + c) / n向下取整的数
最后给出判断完后的最后的X，形式如下：
! x
思路：
二分枚举x在n范围内的偏移量...
具体看看代码吧，也是第一次写交互题...
查看代码
#include <iostream>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
int le = 1,ri = n;
int ls = 0;
while(ri - le > 1)
{
int mid = le + ri >> 1;
int add = n - mid;
printf("+ %d\n",n - mid);
fflush(stdout);
int now;
scanf("%d",&now);
if(now > ls)
ls = now,le = mid;
else ri = mid;
le = (le + n - mid) % n;
ri = (ri + n - mid) % n;
if(ri == 0) ri = n;
}
printf("! %d\n",ls * n + le);
return 0;
}G MinOr Tree
题意：
构成一个最小生成树，但是这里的最小指的是
所有边的或值最小
思路：
想了很久怎么判定当前位可以加入到答案当中...
其实按照上面反过来向就OK了...
从高到低枚举当前位，如果不用当前位依然能够构成生成树，那么我就不给答案累计上这一位所产生的值，并且打一个标记，表示这一位我以后也不会用
查看代码
#include <iostream>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 7;
struct node{
int x,y;
ll w;
node(int x = 0,int y = 0,ll w = 0):x(x),y(y),w(w){}
}a[MAXN];
int fa[MAXN];
int n,m;
void ini()
{for(int i = 1;i <= n;++i) fa[i] = i;}
int Find(int x)
{
if(x == fa[x]) return x;
return fa[x] = Find(fa[x]);
}
bool merge(int x,int y)
{
x = Find(x);
y = Find(y);
if(x != y) {
fa[x] = y;
return 1;
}return 0;
}
ll oth;
bool ok(int x)
{
ini();
int cnt = 0;
for(int i = 1;i <= m;++i)
{
if(((a[i].w >> x) & 1) || (oth & a[i].w)) continue;
if(merge(a[i].x,a[i].y))
cnt += 1;
if(cnt == n - 1) break;
}
return cnt == n - 1;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d %d",&n,&m);
for(int i = 1;i <= m;++i)
scanf("%d %d %lld",&a[i].x,&a[i].y,&a[i].w);
ll ans = 0;
oth = 0;
for(int i = 30;i >= 0;--i)
{
if(!ok(i))
ans |= (1ll << i);//需要用的
else
oth |= (1ll << i);//不用的
}
printf("%lld\n",ans);
}
return 0;
}