A. Salem and Sticks
签.
#include <bits/stdc++.h>
using namespace std; #define N 1010
int n, a[N]; int work(int x)
{
int res = ;
for (int i = ; i <= n; ++i)
res += max(, abs(x - a[i]) - );
return res;
} int main()
{
while (scanf("%d", &n) != EOF)
{
for (int i = ; i <= n; ++i) scanf("%d", a + i);
int Min = (int)1e9, pos = -;
for (int i = ; i <= ; ++i)
{
int tmp = work(i);
if (tmp < Min)
{
Min = tmp;
pos = i;
}
}
printf("%d %d\n", pos, Min);
}
return ;
}
B. Zuhair and Strings
签.
#include <bits/stdc++.h>
using namespace std; #define N 200010
int n, k;
char s[N]; int work(char c)
{
int res = ;
int tmp = ;
for (int i = ; i <= n; ++i)
{
if (s[i] != c) tmp = ;
else
{
++tmp;
if (tmp == k)
{
++res;
tmp = ;
}
}
}
return res;
} int main()
{
while (scanf("%d%d", &n, &k) != EOF)
{
scanf("%s", s + );
int res = ;
for (int i = 'a'; i <= 'z'; ++i)
res = max(res, work(i));
printf("%d\n", res);
}
return ;
}
C. Ayoub and Lost Array
签.
#include <bits/stdc++.h>
using namespace std; #define ll long long
#define N 200010
const ll MOD = (ll)1e9 + ;
int n, l, r;
ll a[], f[N][]; int main()
{
while (scanf("%d%d%d", &n, &l, &r) != EOF)
{
memset(a, , sizeof a);
while (l % && l <= r)
{
a[l % ]++;
++l;
}
while (r % && l <= r)
{
a[r % ]++;
--r;
}
if (l <= r)
{
++a[];
int tmp = (r - l) / ;
a[] += tmp;
a[] += tmp;
a[] += tmp;
}
memset(f, , sizeof f);
f[][] = ;
for (int i = ; i <= n; ++i)
{
f[i][] = (f[i - ][] * a[] % MOD + f[i - ][] * a[] % MOD + f[i - ][] * a[] % MOD) % MOD;
f[i][] = (f[i - ][] * a[] % MOD + f[i - ][] * a[] % MOD + f[i - ][] * a[] % MOD) % MOD;
f[i][] = (f[i - ][] * a[] % MOD + f[i - ][] * a[] % MOD + f[i - ][] * a[] % MOD) % MOD;
}
printf("%lld\n", f[n][]);
}
return ;
}
D. Kilani and the Game
签.
#include <bits/stdc++.h>
using namespace std; #define N 1010
int n, m, p;
char G[N][N];
int s[];
struct node
{
int x, y, step;
node () {}
node (int x, int y, int step) : x(x), y(y), step(step) {}
};
queue <node> q[];
bool stop()
{
for (int i = ; i <= p; ++i) if (!q[i].empty())
return false;
return true;
} int Move[][] =
{
-, ,
, ,
,-,
, ,
};
bool ok(int x, int y)
{
if (x < || x > n || y < || y > m || G[x][y] != '.') return false;
return true;
} void BFS(int id, int cnt)
{
while (!q[id].empty())
{
int x = q[id].front().x;
int y = q[id].front().y;
int step = q[id].front().step;
//printf("%d %d %d %d\n", x, y, id, step);
if (step / s[id] >= cnt) return;
q[id].pop();
for (int i = ; i < ; ++i)
{
int nx = x + Move[i][];
int ny = y + Move[i][];
if (ok(nx, ny))
{
G[nx][ny] = id + '';
q[id].push(node(nx, ny, step + ));
}
}
}
} int main()
{
while (scanf("%d%d%d", &n, &m, &p) != EOF)
{
for (int i = ; i <= p; ++i) scanf("%d", s + i);
for (int i = ; i <= n; ++i) scanf("%s", G[i] + );
for (int i = ; i <= p; ++i) while (!q[i].empty()) q[i].pop();
for (int i = ; i <= n; ++i) for (int j = ; j <= m; ++j) if (isdigit(G[i][j]))
q[G[i][j] - ''].push(node(i, j, ));
int cnt = ;
while ()
{
for (int i = ; i <= p; ++i) BFS(i, cnt);
++cnt;
if (stop()) break;
}
int ans[];
memset(ans, , sizeof ans);
for (int i = ; i <= n; ++i) for (int j = ; j <= m; ++j) if (isdigit(G[i][j]))
++ans[G[i][j] - ''];
//for (int i = 1; i <= n; ++i) printf("%s\n", G[i] + 1);
for (int i = ; i <= p; ++i) printf("%d%c", ans[i], " \n"[i == p]);
}
return ;
}
E. Helping Hiasat
Upsolved.
题意：
两种操作
- 更改自己的handle
- 伙伴查询handle
如果一个伙伴在每次查询时显示的都是自己名字，那么他就会开心
问 最多可以让多少人开心
思路：
法一：
一张图的最大独立集是选出一个点集，使得任意两点不相邻
一张图的最大团是选出一个点集，使得任意两点之间有边相连
一张无向图的补图的最大图就是原图的最大独立集
我们发现这道题两个1之间的所有点都是不能一起happy的，那我们给他们两两之间连上边
然后求补图的最大团即可
#include <bits/stdc++.h>
using namespace std; #define N 110
int n, m, t;
int g[N][N];
int dp[N];
int stk[N][N];
int mx; map <string, int> mp;
int get(string s)
{
if (mp.find(s) != mp.end()) return mp[s];
else mp[s] = t++;
return mp[s];
} int DFS(int n, int ns, int dep)
{
if (ns == )
{
mx = max(mx, dep);
return ;
}
int i, j, k, p, cnt;
for (i = ; i < ns; ++i)
{
k = stk[dep][i];
cnt = ;
if (dep + n - k <= mx)
return ;
if (dep + dp[k] <= mx)
return ;
for (j = i + ; j < ns; ++j)
{
p = stk[dep][j];
if (g[k][p])
stk[dep + ][cnt++] = p;
}
DFS(n, cnt, dep + );
}
return ;
} int clique(int n)
{
int i, j, ns;
for (mx = , i = n - ; i >= ; --i)
{
for (ns = , j = i + ; j < n; ++j)
{
if (g[i][j])
stk[][ns++] = j;
}
DFS(n, ns, );
dp[i] = mx;
}
return mx;
} vector <int> vec;
void add()
{
vec.erase(unique(vec.begin(), vec.end()), vec.end());
for (auto u : vec) for (auto v : vec)
g[u][v] = g[v][u] = ;
vec.clear();
} int main()
{
while (scanf("%d%d", &n, &m) != EOF)
{
t = ;
mp.clear();
for (int i = ; i < m; ++i) for (int j = ; j < m; ++j) g[i][j] = ;
[]()
{
int op; char s[];
for (int nn = ; nn <= n; ++nn)
{
scanf("%d", &op);
if (op == )
add();
else
{
scanf("%s", s + );
vec.push_back(get(s + ));
}
}
}();
add();
for (int i = ; i < m; ++i) g[i][i] = ;
//for (int i = 1; i <= m; ++i) for (int j = 1; j <= m; ++j) printf("%d %d %d\n", i, j, g[i][j]);
printf("%d\n", clique(m));
}
return ;
}
法二：
$m = 40, 可以折半状压，再合起来$
考虑妆压的时候要从子集转移到超集，可以通过$dp上去$
$vp的时候想到折半状压，但是当时是枚举子集来转移，复杂度大大增加..$
#include <bits/stdc++.h>
using namespace std; #define N 50
#define M 1100010
int n, m, t;
int G[N][N]; map <string, int> mp;
int get(string s)
{
if (mp.find(s) != mp.end()) return mp[s];
else mp[s] = ++t;
return mp[s];
} vector <int> vec;
void add()
{
vec.erase(unique(vec.begin(), vec.end()), vec.end());
for (auto u : vec) for (auto v : vec)
G[u][v] = ;
vec.clear();
} int f[M], g[M];
int main()
{
while (scanf("%d%d", &n, &m) != EOF)
{
t = ; mp.clear();
memset(G, , sizeof G);
int op; char s[N];
for (int nn = ; nn <= n; ++nn)
{
scanf("%d", &op);
if (op == ) add();
else
{
scanf("%s", s + );
vec.push_back(get(s + ));
}
}
add();
for (int i = ; i <= m; ++i)
G[i][i] = ;
int s1 = m / , s2 = m - s1;
for (int i = ; i < ( << s1); i <<= ) f[i] = ;
for (int i = ; i < ( << s2); i <<= ) g[i] = ;
f[] = g[] = ;
for (int i = ; i < ( << s1); ++i)
{
for (int j = ; j < s1; ++j) if (!((i >> j) & ))
{
int flag = ;
for (int k = ; k < s1; ++k) if (((i >> k) & ) && G[k + ][j + ])
{
flag = ;
break;
}
f[i | ( << j)] = max(f[i | ( << j)], f[i] + flag);
}
}
for (int i = ; i < ( << s2); ++i)
{
for (int j = ; j < s2; ++j) if (!((i >> j) & ))
{
int flag = ;
for (int k = ; k < s2; ++k) if (((i >> k) & ) && G[s1 + k + ][s1 + j + ])
{
flag = ;
break;
}
g[i | ( << j)] = max(g[i | ( << j)], g[i] + flag);
}
}
int res = ;
for (int i = ; i < ( << s1); ++i)
{
int s3 = ( << s2) - ;
for (int j = ; j < s1; ++j) if ((i >> j) & )
{
for (int k = ; k < s2; ++k) if (G[j + ][s1 + k + ] && ((s3 >> k) & ))
s3 ^= ( << k);
}
res = max(res, f[i] + g[s3]);
}
printf("%d\n", res);
}
return ;
}
法三：
为什么随机也行啊，能不能证明啊，喵喵喵..
#include <bits/stdc++.h>
using namespace std; #define ll long long
#define N 50
int n, m, t;
int G[N][N], a[N];
ll f[N]; map <string, int> mp;
int get(string s)
{
if (mp.find(s) != mp.end()) return mp[s];
else mp[s] = ++t;
return mp[s];
} vector <int> vec;
void add()
{
vec.erase(unique(vec.begin(), vec.end()), vec.end());
for (auto u : vec) for (auto v : vec)
G[u][v] = ;
vec.clear();
} int main()
{
while (scanf("%d%d", &n, &m) != EOF)
{
t = ; mp.clear();
memset(G, , sizeof G);
int op; char s[N];
for (int nn = ; nn <= n; ++nn)
{
scanf("%d", &op);
if (op == ) add();
else
{
scanf("%s", s + );
vec.push_back(get(s + ));
}
}
add();
for (int i = ; i <= m; ++i)
G[i][i] = ;
int res = ;
for (int i = ; i <= m; ++i) a[i] = i;
for (int i = ; i <= m; ++i)
{
f[i] = ;
for (int j = ; j <= m; ++j) if (G[i][j])
f[i] |= (1ll << (j - ));
}
for (int t = ; t <= ; ++t)
{
random_shuffle(a + , a + + m);
ll g = ; int tmp = ;
for (int i = ; i <= m; ++i) if (((g >> (a[i] - )) & 1ll) == )
{
g |= f[a[i]];
++tmp;
}
res = max(res, tmp);
}
printf("%d\n", res);
}
return ;
}