题目来源： ICPC Central Europe Regional Contest 2019
A. AAB
找最长后缀回文串
思路：
KMP，正串和逆串匹配
#include<bits/stdc++.h>
using namespace std;
string s,p;
int n;
const int maxn = 4e5+10;
int nxt[maxn];
int main(){
ios::sync_with_stdio(0);
cin >> n;
cin >> s;
p = s;
reverse(p.begin(),p.end());
nxt[0] = -1;
int j = 0, k = -1;
int m = n;
while (j < m) {
if (k == -1 or s[j] == s[k]) nxt[++j] = ++k;
else k = nxt[k];
}
int i = 0;
j = 0;
int ans = 1;
while (i < n) {
if (j == -1 or s[i] == p[j]) {
i++; j++;
if(i == n){
ans = max(ans,j);
}
}
else {
j = nxt[j];
}
}
cout << n - ans << endl;
}
也可以用马拉车，注意要开两倍空间
#include<bits/stdc++.h>
using namespace std;
string s,t;
int n;
const int maxn = 1e6+10;
int p[maxn];
int main(){
ios::sync_with_stdio(0);
cin >> n;
cin >> s;
t = "$";
for(int i = 0;i < n;i++){
t += "#" + s.substr(i,1);
}
t += "#@";
n = t.length();
int ans = 1;
int c = 0,r = 0;
for(int i = 1;i < n - 1;i++){
p[i] = i < r ? min(p[2*c-i],r-i) : 1;
while(t[i-p[i]] == t[i+p[i]])p[i]++;
if(i+p[i] > r){
r = p[i] + i;
c = i;
}
if( (i - p[i] + 1) / 2 + p[i] - 1 == s.size()){
ans = max(ans,p[i]-1);
}
}
cout << s.size() - ans << endl;
}
C. Bob in Wonderland
拆链，思维题
队友的代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//typedef __int128 lll;
#define print(i) cout << "debug: " << i << endl
#define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, b) memset(a, b, sizeof(a))
const ll mod = 1e9 + 7;
const int maxn = 2e6;
const int inf = 0x3f3f3f3f;
int d[maxn];
int main()
{
int n; cin >> n;
for(int i = 1; i < n; i++)
{
int a, b; scanf("%d%d", &a, &b);
d[a]++, d[b]++;
}
int res = 0;
for(int i = 1; i <= n; i++)
if(d[i] >= 3)
res += (d[i] - 2);
cout << res << endl;
}
D. Deep800080
计算几何
转换成线段的交，注意排序规则
不知道为什么用 %d 输入再强制类型转换过不去？？一直卡 98.94%
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
int n;
double r, a, b;
const double pi = acos(-1.0);
const double eps = 1e-8;
int sgn(double x) {
if (fabs(x) < eps)return 0;
if (x > 0)return 1;
else return -1;
}
struct Point {
double x, y;
int val;
Point() {}
Point(double _x, double _y) {
x = _x;
y = _y;
val = 0;
}
double distance(Point p) {
return sqrt((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y));
}
bool operator <(const Point& b)const {
//左下小
if (sgn(x - b.x) == 0) {
if (sgn(y - b.y) == 0) {
return val > b.val;
}
return y < b.y;
}
return x < b.x;
}
Point operator +(const Point& b)const {
return Point{ x + b.x, y + b.y };
}
Point operator *(const double& k)const {
return Point{ x * k, y * k };
}
Point operator /(const double& k)const {
return Point{ x / k, y / k };
}
Point operator -(const Point& b)const {
return Point{ x - b.x,y - b.y };
}
double operator *(const Point& b)const {
return x * b.x + y * b.y;
}
double len() {
return hypot(x, y);
}
double len2() {
return x * x + y * y;
}
};
struct Line {
Point s, e;
Line() {}
Line(Point _s, Point _e) {
s = _s;
e = _e;
}
Point lineProg(Point p) {
return s + (((e - s) * ((e - s) * (p - s))) / ((e - s).len2()));
}
double angle() {
double k = atan2(e.y - s.y, e.x - s.x);
if (sgn(k) < 0) k += pi;
if (sgn(k - pi) == 0) k -= pi;
return k;
}
};
vector<Point>A;
int main() {
//scanf("%d%d%d%d") ???? %d 输入再强转就wa????
scanf("%d%lf%lf%lf", &n, &r, &a, &b);
Line l = Line(Point(0, 0), Point(a, b));
double angle = l.angle();
for (int i = 0; i < n; i++) {
double x, y;
scanf("%lf%lf", &x, &y);
Point u = l.lineProg(Point{ x,y });
double d = u.distance(Point{ x,y });
if (sgn(d - r) > 0)continue;
double t = sqrt(r * r - d * d);
Point a = Point{ u.x + cos(angle) * t,u.y + sin(angle) * t };
Point b = Point{ u.x - cos(angle) * t,u.y - sin(angle) * t };
if (a < b) { a.val = 1; b.val = -1; }
else { a.val = -1; b.val = 1; }
A.push_back(a);
A.push_back(b);
}
sort(A.begin(), A.end());
int ans = 0, sum = 0;
for (Point x : A) {
sum += x.val;
ans = max(ans, sum);
}
printf("%d
", ans);
}
E. Zeldain Garden
(d(n)) 前缀和，不用筛，简单分块
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll solve(ll n){
ll ans = 0;
for(ll l = 1,r;l <= n;l = r + 1){
r = n / (n / l);
ans += (r-l+1)*(n/l);
}
return ans;
}
int main(){
ll x,y;
cin >> x >> y;
cout << solve(y) - solve(x-1) << endl;
}
F. Light Emitting Hindenburg
二进制，简单模拟
题目的锅，是 (2^{30-L}) ，其实就是二进制表示
其实就是 (n) 个数里面挑 (m) 个数，使得他们相与（&）最大
从高位往低位挑就可以
#include<bits/stdc++.h>
using namespace std;
int n,k,x;
const int N = 2e5+10;
int bt[40][N];
int vis[40][N];
int main(){
scanf("%d%d",&n,&k);
for(int i = 1;i <= n;i++){
scanf("%d",&x);
for(int j = 0;j < 31;j++){
if(x & (1 << j)){
bt[j][i] = 1;
}
}
}
int ans = 0;
int t = 1;
for(int j = 30;j >= 0;j--){
int cnt = 0;
for(int i = n;i >= 1;i--){
if(vis[j+1][i] == t - 1 and bt[j][i] == 1){
cnt++;
}
vis[j][i] = vis[j+1][i];
}
if(cnt >= k){
ans += (1<<j);
for(int i = n;i >= 1;i--){
if(vis[j+1][i] == t - 1 and bt[j][i] == 1){
vis[j][i] = t;
}
}
t++;
}
}
printf("%d
",ans);
}
G. K == S
AC自动机 ，矩阵快速幂
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 7e5 + 10;
queue<int>q;
const int mod = 1e9 + 7;
struct Mat {
int m[500][500], n;
Mat(int _n,int v) {
n = _n;
memset(m, 0, sizeof m);
for (int i = 0; i < n; i++)m[i][i] = v;
}
Mat operator *(const Mat& b)const {
Mat res = Mat(b.n,0);
int n = b.n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
res.m[i][j] = (res.m[i][j] + m[i][k] * b.m[k][j]) % mod;
}
}
}
return res;
}
};
struct {
int c[N][26], fail[N], val[N], cnt;
void insert(char* s) {
int len = strlen(s); int now = 0;
for (int i = 0; i < len; i++) {
int v = s[i] - 'a';
if (!c[now][v])c[now][v] = ++cnt;
now = c[now][v];
}
//val[now]++;
val[now] = 1;
}
void getFail() {
for (int i = 0; i < 26; i++) {
if (c[0][i])fail[c[0][i]] = 0, q.push(c[0][i]);
//***
else c[0][i] = 0;
}
while (!q.empty()) {
int u = q.front(); q.pop();
//***
if (val[fail[u]] == 1) {
val[u] = 1;
}
for (int i = 0; i < 26; i++) {
if (c[u][i]) {
fail[c[u][i]] = c[fail[u]][i];
q.push(c[u][i]);
}
else c[u][i] = c[fail[u]][i];
}
}
}
int query(char* s) {
int len = strlen(s); int now = 0, ans = 0;
for (int i = 0; i < len; i++) {
now = c[now][s[i] - 'a'];
for (int t = now; t && val[t] != -1; t = fail[t]) {
ans += val[t];
val[t] = -1;
}
}
return ans;
}
Mat getMat() {
//这里 cnt 也能过，但是上面的POJ会wa，这里数据的问题，应该是cnt+1
Mat res = Mat(cnt + 1, 0);
for (int i = 0; i <= cnt; i++) {
for (int j = 0; j < 26; j++) {
if (!val[c[i][j]]) {
res.m[i][c[i][j]]++;
}
}
}
return res;
}
}Ac;
Mat qpow(Mat a, int p) {
Mat res = Mat(a.n, 1);
while (p) {
if (p & 1) res = a * res;
a = a * a;
p >>= 1;
}
return res;
}
int n;
char p[N];
signed main() {
int n, m, x;
scanf("%lld%lld", &n, &m);
for (int i = 0; i < m; i++) {
scanf("%lld%s", &x, p);
Ac.insert(p);
}
Ac.getFail();
Mat mat = Ac.getMat();
mat = qpow(mat, n);
int ans = 0;
for (int i = 0; i < mat.n; i++) {
ans = (ans + mat.m[0][i]) % mod;
}
printf("%lld
", ans);
}
H. Ponk Warshall
拆环
这份dfs的代码MLE 了，就改成了暴力拆
/*
* Status： MLE
*/
#include<bits/stdc++.h>
using namespace std;
map<char, int>mp;
int G[5][5];
int out[5];
const int N = 1e6+10;
char s[N],t[N];
int ans;
void dfs(int u, int len, int target) {
if (u == target and len != -1) {
ans += len;
return;
}
for (int i = 1; i <= 4; i++) {
if (G[u][i] > 0) {
dfs(i, len + 1, target);
G[u][i]--;
out[u]--;
}
}
}
int main() {
mp['A'] = 1; mp['C'] = 2;
mp['G'] = 3; mp['T'] = 4;
scanf("%s",s);
scanf("%s",t);
int n = strlen(s);
for (int i = 0; i < n; i++) {
G[mp[s[i]]][mp[t[i]]]++;
out[mp[s[i]]]++;
}
for (int i = 1; i <= 4; i++) {
while (out[i] != 0) {
dfs(i, -1, i);
}
}
printf("%d
",ans);
}
#include<bits/stdc++.h>
using namespace std;
map<char, int>mp;
int G[5][5];
int out[5];
const int N = 1e6 + 10;
char s[N], t[N];
int ans;
int main() {
mp['A'] = 1; mp['C'] = 2;
mp['G'] = 3; mp['T'] = 4;
scanf("%s", s);
scanf("%s", t);
int n = strlen(s);
for (int i = 0; i < n; i++) {
G[mp[s[i]]][mp[t[i]]]++;
}
for (int i = 1; i <= 4; i++) {
while (G[i][i])G[i][i]--;
}
for (int i = 1; i <= 4; i++) {
for (int j = i + 1; j <= 4; j++) {
while (G[i][j] and G[j][i]) {
G[i][j]--; G[j][i]--;
ans++;
}
}
}
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 4; j++) {
for (int k = 1; k <= 4; k++) {
if (i == j or j == k or k == i)continue;
while (G[i][j] and G[j][k] and G[k][i]) {
G[i][j]--; G[j][k]--; G[k][i]--;
ans += 2;
}
}
}
}
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 4; j++) {
if (i == j)continue;
for (int k = 1; k <= 4; k++) {
if (k == i or k == j)continue;
for (int u = 1; u <= 4; u++) {
if (u == i or u == j or u == k)continue;
while (G[i][j] and G[j][k] and G[k][u] and G[u][i]) {
G[i][j]--; G[j][k]--; G[k][u]--; G[u][i]--;
ans += 3;
}
}
}
}
}
printf("%d
", ans);
}
J. The Bugs
稍微复杂一点的模拟+RMQ