正睿提高十连测day1——2018.8.25

比赛总结

1

找规律。最优一定是围成六边形。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cctype>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
typedef long long LL;
const int N = 1000100;
LL f[N], g[N];
int cnt;
void init() {
    f[1] = 1;f[2] = 6;
    g[1] = 1;g[2] = 7;
    for (cnt=3; cnt<=1000000; ++cnt) {
        f[cnt] = f[cnt - 1] + 6;
        g[cnt] = g[cnt - 1] + f[cnt];
    }
}
int main() {
    LL n; cin >> n;
    init();
    if (n == 1) {
        cout << 6; return 0;
    }
    LL t, t2, tmp;
    for (int i=1; i<=cnt; ++i) {
        if (g[i] == n) {
            cout << f[i + 1]; return 0;
        }
        else if (g[i] > n) { 
            t = i - 1;
            break;
        }
    }
    LL r = n - g[t], m = t, ans = 0;
    if (r <= (m - 1)) {
        ans += (f[t + 1] - r) + r + 1;
    }
    else {
//      tmp = r - (m - 1);
        t2 = r / m;
        ans += (f[t + 1] - r) + r + t2 + 1;
    }
    cout << ans;
    return 0;
}

T2

按钮i连向一个物品j，那么增加一条(j->i)的边，说明按完j按钮后才能按i（先按i的话，j就不能按了），（自己连向自己的可以跳过，直接统计答案，防止自环）。
如果物品j有多个连向的按钮，按最大的。
然后每个按钮指向一个物品，每个物品最多一个按钮。所以是一条链或者一个环。链上的情况是都能取到的（全部按完）。
而环上的一个物品是不能取到的，他可以由连向它的第二大的取。每个物品在记录连向它的第二大的边。于是在这些第二大的边中找最大的（可能没有）。

这个地方考试时想错了，每条边只连向最大的，所以形成了基环树。（开始没想到，最后想到后，没时间改了，T1做的太长了。）

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cctype>
using namespace std;
typedef long long LL;
inline int read() {
    int x = 0, f = 1; char ch = getchar(); for (; !isdigit(ch); ch=getchar()) if (ch=='-') f = -1;
    for (; isdigit(ch); ch=getchar()) x = x * 10 + ch - '0'; return x * f;
}
const int N = 200100;
int f[N], vis[N];
LL c[N], d[N], a[N], fir[N], sec[N];
int Now_Color;
LL Answer, Min;
void dfs(int u) {
    if (vis[u] == Now_Color) { Answer -= Min; return ;}
    if (vis[u]) return ;
    vis[u] = Now_Color;
    if (fir[u]) {
        Answer += 1ll * c[fir[u]] * a[u];
        Min = min(Min, c[fir[u]] - c[sec[u]]);
        if (fir[u] != u) dfs(fir[u]);
    }
}
int main() {
    int n = read();
    for (int i=1; i<=n; ++i) 
        f[i] = read(), c[i] = read(), d[i] = read(), a[i] = read();
    for (int i=1; i<=n; ++i) {
        c[i] = d[f[i]] - c[i];
        if (c[i] > c[fir[f[i]]]) sec[f[i]] = fir[f[i]], fir[f[i]] = i;
        else if (c[i] > c[sec[f[i]]]) sec[f[i]] = i;
    }
    for (int i=1; i<=n; ++i) 
        if (!vis[i]) ++Now_Color, Min = 1e9, dfs(i);
    cout << Answer;
    return 0;
}

T3

n^2枚举一个字符串，（优化：预处理n的因数），然后判断（优化：根据字符的个数）。

判断：
转化，插入一个字符串->消光字符串。
设枚举的原始串为p，长度为len
发现原始串p被分为几段后，中间的每一段都是可以独立消光的一段。
原始串为，a....b....cd，原始串被划为3段，但中间的都是可以消光。
f[i][j]表示i~j是否合法。
如果j-i+1为len：则表示能否消光。
否则表示多余的部分是否是p的前缀（也就是去掉所有可以消掉的，剩下的合起来是p的前缀a.....b....c，去掉所有消掉的，还剩abc是abcd的前缀，所以合法）

然后可以加一个字符一个字符的加，然后判断新的形成的区间是否合法（就是f[i][j]从f[i][j-1]转移，f[i][j-1]合法了，加入字符j，判断f[i][j]），如果加上这个字符，和剩下的还是可以组成p的后缀，那么就是合法的。
当然还有一种情况就是就是最后加入一个字符后，使得字符串形成了一个以j结尾的，长度为len*k的可以消掉的字符串，那么前面的就可以和这个字符串合起来了。就是f[i][j-len*k]（合法）和f[j-len*k+1][j]合起来，f[i][j]就是合法的，当前的前缀就是f[i][j-len*k]的剩余的字符。
样例abaabcdbcd，最后加入d后，后面8个形成了可消，和前面ab合起来就行了。
详见代码

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cctype>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
typedef long long LL;
inline int read() {
    int x = 0, f = 1; char ch = getchar(); for (; !isdigit(ch); ch=getchar()) if (ch=='-') f = -1;
    for (; isdigit(ch); ch=getchar()) x = x * 10 + ch - '0'; return x * f;
}
const int N = 205;
const int mod = 12582917;
const int Base = 131;
bool vis[mod + 10];
int f[N][N], cnt1[N], cnt2[N], num[N];
char p[N], s[N], ans[N];
int n;
vector<int> q;
int getHash(int len) {
    int ans = 0;
    for (int i=1; i<=len; ++i) 
        ans = 1ll * ans * Base % mod + (p[i] - 'a' + 1) % mod;
    return ans;
}
void Update(int len) {
    if (ans[1] == '#') 
        for (int i=1; i<=len; ++i) ans[i] = p[i];
    else {
        for (int i=1; i<=len; ++i) if (p[i] > ans[i]) return ;
        for (int i=1; i<=len; ++i) ans[i] = p[i];
    }
}
bool Solve(int len) {
    for (int i=1; i<=n; ++i) f[i][i] = s[i]==p[1];
    for (int L=2; L<=n; ++L) {
        for (int i=1,j; (j=i+L-1)<=n; ++i) {
            f[i][j] = 0;
            if (f[i][j - 1] && s[j]==p[(L-1)%len+1]) f[i][j] = 1;
            else if(s[j]==p[len]) for (int k=1; i+k*len<=j; ++k) {
                if (f[i][j-k*len] && f[j-k*len+1][j]) {f[i][j] = 1; break; }
            }
        }
    }
    return f[1][n];
}
bool getsub(int l,int len) {
    for (int i='a'; i<='z'; ++i) cnt2[i] = 0;
    for (int i=1; i<=len; ++i) p[i] = s[l + i - 1], cnt2[p[i]] ++;
    for (int i='a'+1; i<='z'; ++i) if (cnt2[i] && cnt1[i] % cnt2[i]) return false;
    int H = getHash(len);
    if (vis[H]) return false;
    vis[H] = true; q.push_back(H);
    return true;
}
int main() {
    int Case = read();
    while (Case --) {
        scanf("%s", s + 1);
        n = strlen(s + 1);
        ans[1] = '#';
        for (int i=1; i<=n; ++i) ++cnt1[s[i]];
        int tot = 0;
        for (int i=1,lim=sqrt(n); i<=lim; ++i) 
            if (n % i == 0) {
                num[++tot] = i;
                if (n / i != i) num[++tot] = n / i;
            }
        sort(num + 1, num + tot + 1);
        for (int t=1,len=num[t]; t<=tot; len=num[++t]) {
            for (int l=1; (l+len-1)<=n; ++l) {
                if (!getsub(l, len)) continue;
                if (Solve(len)) Update(len);
            }
            if (ans[1] != '#') {
                for (int i=1; i<=len; ++i) putchar(ans[i]); puts(""); break;
            }
        }
        for (int i='a'; i<='z'; ++i) cnt1[i] = 0;
        for (int i=0,sz=q.size(); i<sz; ++i) vis[q[i]] = false;
        q.clear();
    }
    return 0;
}