文章目录
- B Bitwise Exclusive-OR Sequence
- E Edward Gaming, the Champion
- J Luggage Lock
- H Line Graph Matching
- M String Problem 字符串，后缀自动机
题目地址 第 46 届 ICPC 国际大学生程序设计竞赛亚洲区域赛（沈阳）
B Bitwise Exclusive-OR Sequence
题目地址B Bitwise Exclusive-OR Sequence
题目大意:给你一个n以及m，n代表变量的个数，m代表限制方程的个数，接下来给出m行，每行3个数a,b,c代表第a个变量和第b个变量的异或值为c，问n个变量的最小和是多少，如果异或方程出现矛盾，则直接输出-1。
思路：首先可能是多个图， 对于每个图中的每一位， 取0 或者取1 都是可以确定图上的其他数字取0 或者取1 。 所以我们可以去枚举取0 或者取1 ，来取个min 得到结果。
所以这里我们用并查集， 最大数为 2的30次， 所以我们对于每一位都做一个并查集， 就是30个并查集。 f[a] 表示当前位置取1 f[a+n] 表示当前位取0
这样就可以枚举区间了
AC代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5+10;
LL n, m, fa[N], sz[N];
LL a[N];
struct Node
{
LL a, b;
LL val;
}num[N];
LL find(LL x)
{
if(fa[x] != x) fa[x] = find(fa[x]);
return fa[x];
}
void init()
{
for(LL i = 1; i <= n; i ++)
{
fa[i] = i, sz[i] = 1;
fa[i+n] = i+n, sz[i+n] = 0;
}
}
void merge(LL a, LL b)
{
sz[a] += sz[b];
fa[b] = a;
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= m; i ++)
{
scanf("%lld%lld%lld", &num[i].a, &num[i].b, &num[i].val);
}
LL res = 0;
for(int i = 0; i < 30; i ++)
{
init(); // 每一次做并查集都要初始化！
for(int j = 1; j <= m; j ++)
{
int aa = find(num[j].a);
int bb = find(num[j].b);
int aaa = find(num[j].a + n);
int bbb = find(num[j].b + n);
if((num[j].val >> i) & 1 ) // 不同为1 ，一个取0一个取1
{
if(aa == bb)
{
cout << -1 << endl;
return 0;
}
if(aa == bbb) continue;
merge(aa, bbb);
merge(bb, aaa);
}
else // 相同为0， 都取1 或者都取0
{
if(aa == bbb )
{
cout << -1 << endl;
return 0;
}
if(aa == bb) continue;
merge(bb, aa);
merge(bbb, aaa);
}
}
for(int j = 1; j <= n; j ++) // 对于每个数字计算结果
{
res += (LL)min(sz[find(j)], sz[find(j+n)]) * (1 << i);
sz[find(j)] = 0;
sz[find(j+n)] = 0;
}
}
cout << res << endl;
return 0;
}
E Edward Gaming, the Champion
题目地址 E Edward Gaming, the Champion
题目大意：给出一个很长的字符串，判断"edgnb"在里面出现了几次
思路：KMP模板，直接套就行
AC代码:
#include <bits/stdc++.h>
#define int long long
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=2e5+10;
int ans,P[maxn];
char A[maxn],B[maxn]= {"\0edgnb"};
//这里的A和B串以1开始存储
void Pre() {
int j=0,m=strlen(B+1);
P[1]=0;
for(int i=1; i<m; i++) {
while(j>0&&B[i+1]!=B[j+1])
j=P[j];
if(B[i+1]==B[j+1])
j++;
P[i+1]=j;
}
}
int KMP() {
int j=0,n=strlen(A+1),ans=0,m=strlen(B+1);
for(int i=0; i<n; i++) {
while(j>0&&A[i+1]!=B[j+1])
j=P[j];
if(A[i+1]==B[j+1])
j++;
if(j==m) {//匹配成功，记录数量并且清零
ans++;
j=0;
}
}
return ans;
}
signed main() {
scanf("%s",A+1);
Pre();
cout <<KMP();
return 0;
}
J Luggage Lock
题目地址J Luggage Lock
题目大意：给出一个4位密码锁，每次只能一次性多个滑动相邻的位置向上或向下移动一格，现在给出多次询问，每次询问给出一个初始值和终点值，询问两者间的最少操作数
思路：可以观察到，无论初始点和终点值是多少，如aaaa,bbbb，最后都可以等效成从0000 到(b-a)(b-a)(b-a)(按位操作，取模)，那么从0000点开始求出其到其他所有状态的操作数并记录，直接BFS，对于给出的询问直接等效成从0000出发即可
AC代码
#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const int N=1e5+5;
vector<int> mm[N];
int dis[N];
bool flag[N];
void init(int n)
{
int a[4]={0},b[4];
int cnt = 0;
int x = n;
while(n)
{
a[cnt]=n%10;
n/=10;
cnt++;
}
int t = 0;
for(int i = 1;i <= 4;i++)
{
for(int j = 0;j < 5-i;j++)
{
for(int k = 0;k < 4;k ++)
{
b[k]=a[k];
}
for(int k = j;k < j+i;k++)
{
b[k]=(a[k]+1)%10;
}
for(int tt = 3;tt >= 0;tt--)
{
t=t*10+b[tt];
}
mm[x].push_back(t);
t = 0;
for(int k = j;k < j+i;k++)
{
b[k]=(a[k]-1+10)%10;
}
for(int tt = 3;tt >= 0;tt--)
{
t=t*10+b[tt];
}
mm[x].push_back(t);
t = 0;
}
}
}
void BFS()
{
int d=1;
queue<int> q;
q.push(0);
while(!q.empty())
{
int leng = q.size();
while(leng--)
{
int t = q.front();
q.pop();
int n = mm[t].size();
for(int i = 0;i < n;i++)
{
if(!flag[mm[t][i]])
{
dis[mm[t][i]]=d;
q.push(mm[t][i]);
flag[mm[t][i]]=true;
}
}
}
d++;
}
}
void solve()
{
int a,b;
scanf("%d%d",&a,&b);
if(a==b)
{
printf("0\n");
return;
}
int aa[4]={},bb[4]={},cc[4];
int cnt=0;
while(a)
{
aa[cnt++]=a%10;
a/=10;
}
cnt=0;
while(b)
{
bb[cnt++]=b%10;
b/=10;
}
for(int i = 0;i < 4;i++)
{
cc[i]=(bb[i]-aa[i]+10)%10;
}
int t = 0;
for(int i = 3;i >=0;i--)
{
t=t*10+cc[i];
}
printf("%d\n",dis[t]);
}
int main()
{
// freopen("in.txt","r",stdin);
// int t = 1;
int t;
scanf("%d",&t);
for(int i = 0;i<=9999;i++)
{
init(i);
}
BFS();
while(t--)
{
solve();
}
return 0;
}
H Line Graph Matching
题目地址H Line Graph Matching
给定一个无向带权图，将其所有的 边看作点，点看作边 构建出新图也是一个无向带权图（两点之间的边权为这两点的权值（原边权）相加），求这个新图上的最大独立边集 —— 选取所有 不相邻 的边构成的集合保证权值累加Max
思路：
- 首先需要理解的是，选取新图任意一条边 == 选取原图中的两条相邻边（权值）；
- 若选取新图中两条相邻边，它们肯定会共享一个点，这个点相当于原图的同一条边，会产生交集；
- 题意是不能选取相邻边的，所以我们在 新图要求的最大独立边集 == 原图中选取不重复相邻边配对，尽可能权值和Max
- 细节分析
AC代码:
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define sca scanf
#define pri printf
#define ul (u << 1)
#define ur (u << 1 | 1)
#define forr(a,b,c) for(int a=b;a<=c;a++)
#define rfor(a,b,c) for(int a=b;a>=c;a--)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef unsigned long long ull;
const int N = 100010, M = 200010, MM = N;
int INF = 0x3f3f3f3f, mod = 1e9 + 7;
ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, k, T, S, D;
int p[N], f[N];
struct edge
{
int a, b, x;
bool operator<(const edge& ee)const { return x > ee.x; }
}ed[M];
int find(int x) {
if (p[x] != x)p[x] = find(p[x]);
return p[x];
}
int main() {
cinios;
cin >> n >> m;
forr(i, 1, n)p[i] = i;
forr(i, 1, m) {
int a, b, x;
cin >> a >> b >> x;
ed[i] = { a,b,x };
}
sort(ed + 1, ed + 1 + m);//贪心每次选取尽可能大的边去配对
ll ans = 0;//配对成功一对边我们就可以累计在贡献里
forr(i, 1, m) {
int a = ed[i].a, b = ed[i].b, w = ed[i].x;
a = find(a), b = find(b);
if (a == b) { //若在同一连通块
if (!f[a])f[a] = w;//无配对
else ans += w + f[a], f[a] = 0;
//有配对就配
}
else {
if (!f[a] && !f[b])f[b] = f[a] = w;//两边都无配对，现有的边可以放此块中等候配对
else { //否则只要有一边有配对
ans += w + max(f[a], f[b]); //显然是优先和大的配
f[a] = f[b] = min(f[a], f[b]);//小的继续等候
}
p[a] = b;
}
}
cout << ans;
return 0;
}
M String Problem 字符串，后缀自动机
题目地址M String Problem
题目大意:输出字典序最小最大开始的序列编号以及出现过几次；
思路：遇到字典序问题，考虑利用后缀自动机来解.
静态问题可以沿着后缀自动机的字符边贪心走大的.
那么不妨先维护出前缀 i 的答案，然后考虑下一位的影响.
显然，如果影响的话一定是下一位的字母被加入答案，那么在后缀自动机中就是答案中深度最小的点改变.
改变成的新点一定是加入 i+1 字符时所影响的新点，而所有新点总和是 O(n) 的.
由于后缀自动机的构建方式，在线做是不现实的，不妨离线构建完后缀自动机然后记录每个点最早出现位置.
最后开一个数组统计并离线下来即可.
AC代码:
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define N 2000009
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
char str[N];
int n, last, tot, fir[N], len[N], st[N], ch[N][26], pre[N], dep[N], vis[N], tail, a[N];
struct data {
int p, c;
data(int p = 0, int c = 0):p(p), c(c){}
};
vector<data>G[N];
void extend(int c, int pos) {
int np = ++ tot, p = last;
len[np] = len[p] + 1, last = np;
fir[np] = pos;
for(; p && !ch[p][c]; p = pre[p]) {
ch[p][c] = np;
}
if(!p) pre[np] = 1;
else {
int q = ch[p][c];
if(len[q] == len[p] + 1) pre[np] = q;
else {
int nq = ++ tot;
len[nq] = len[p] + 1;
fir[nq] = fir[q];
memcpy(ch[nq], ch[q], sizeof(ch[q]));
pre[nq] = pre[q], pre[np] = pre[q] = nq;
for(; p && ch[p][c] == q; p = pre[p])
ch[p][c] = nq;
}
}
}
int main() {
// setIO("input");
scanf("%s", str + 1);
n = strlen(str + 1);
last = tot = 1;
for(int i = 1; i <= n ; ++ i) {
extend(str[i] - 'a', i);
}
for(int i = 1; i <= tot; ++ i) {
for(int j = 0; j < 26; ++ j) {
if(ch[i][j]) {
int q = ch[i][j];
G[fir[q]].pb(data(i, j));
}
}
}
vis[1] = 1, a[++ tail] = 1, st[1] = -1;
for(int i = 1; i <= n ; ++ i) {
int mk = 0, de = 0;
for(int j = 0; j < G[i].size() ; ++ j) {
data e = G[i][j];
if(vis[e.p] && e.c > st[e.p]) {
if(mk == 0) {
mk = e.p, de = dep[e.p];
}
else if(dep[e.p] < de) {
mk = e.p, de = dep[e.p];
}
}
}
if(mk) {
while(a[tail] != mk)
vis[a[tail]] = 0, -- tail;
st[mk] = str[i] - 'a';
a[++ tail] = ch[mk][str[i] - 'a'], dep[a[tail]] = tail, vis[a[tail]] = 1, st[a[tail]] = -1;
}
printf("%d %d\n", i - tail + 2, i);
}
return 0;
}
