六校联考day2——2018.8.30

比赛总结

预计100 + 100 + 30+（写了2^n次方搜索，居然过了大样例，对于有些数据可以过）
实际70 + 50 + 50

T1

想O(n)的算法没想出，于是想了一个复杂度比nlogn小些的复杂度。
一个点作为贡献，且作为右端点，那么只要在前面找到一个大于它的数，且这个数最远就可以了。
对于前面两个可能作为左端点的数x,y，假设x在前，那么如果y < x，y就不会作为左端点。
如果当前的右端点数z，若z < y那么x和y都可以作为左端点，而x在y前面，它的区间就长，所以x更优。
如果z > y && z < x，x可以作为左端点。
（如果z > x，那么x,y都不可以作为左端点。）
所以用一个数组记录到当前位置上升的数，在这里面二分出第一个大于这个数的数，并找到这个位置；如果当前数大于数组中最大的数，那么加入当前数，continue。
之后要把原数组反过来在做一遍，一开始忘了，过不了大样例，小样例对拍没发现问题，居然以为大样例错了。。。后来用n^2的暴力跑了70多秒（开O2的29左右），跑出答案，发现大样例没错。于是又继续调，发现了这个问题。
T1做完时9点左右。最后特判了一个n<=1000的数据，把暴力程序复制过来了。然而程序这样写的。

int main() {
    int n = read();
    if (n <= 1000) { solve1(n); return 0; }
    for (int i=1; i<=n; ++i) a[i] = read();

发现没读入，最后用文件试了一下大样例，没试小样例。
以后所有样例都用文件试一遍。
还有一个低级错误，开始想1e6的数据很大，于是写了fread，但是为了调试，先注释了，最后也没有上。

#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;
// char buf[100000], *p1, *p2;
// #define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
// inline int read() {
//  int x = 0, f = 1; char ch = nc(); for (; !isdigit(ch); ch=nc()) if (ch=='-') f = -1;
//  for (; isdigit(ch); ch=nc()) x = x * 10 + ch - '0'; return x * f;
// }
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 = 1000010;
int a[N], q[N], s[N];
void solve1(int n) {
    LL Ans = 0;
    for (int i=1; i<=n; ++i) {
        for (int j=i; j<=n; ++j) {
            int t = min(a[i], a[j]);
            Ans = max(Ans, 1ll * (j - i + 1) * t);
        }
    }
    cout << Ans;
}
LL solve2(int n) {
    int Top = 1;
    LL Ans = 0;
    q[1] = a[1], s[1] = 1;
    for (int i=2; i<=n; ++i) {
        if (a[i] > q[Top]) {
            q[++Top] = a[i], s[Top] = i;
            continue;
        }
        int L = 1, R = Top, pos = -1, mid;
        while (L <= R) {
            mid = (L + R) >> 1;
            if (q[mid] >= a[i]) pos = s[mid], R = mid - 1;
            else L = mid + 1;
        }
        Ans = max(Ans, 1ll * (i - pos + 1) * a[i]);
    }
    return Ans;
}
int main() {
//  freopen("1.txt","r",stdin);
    freopen("w.in","r",stdin);
    freopen("w.out","w",stdout);
    int n = read();
    LL Ans = 0;
    for (int i=1; i<=n; ++i) a[i] = read(), Ans = max(Ans, (LL)a[i]);
    Ans = max(Ans, solve2(n));
    for (int i=1; i<=n; ++i) s[i] = a[i];
    for (int i=1; i<=n; ++i) a[i] = s[n - i + 1];
    Ans = max(Ans, solve2(n));
    cout << Ans;
    return 0;
}

T2

开始半小时读题的时候，想到了一个做法，9点写完T1，然后来写T2，20分钟左右写完，过了大样例。
然后居然又没取模！！！少了50分。

摘自题解：
这种操作是一定做了比没做优的。
$a ^ 2 + b^2$
设$a | b = a + c, a \& b = b - c$
$(a + c) ^ 2 + (b - c) ^ 2 = a^2 + 2ac + c^2 + b^2 - 2bc + c ^ 2 = a^2 + b^2+2c(c+a-b)$
$c + a = a|b, \ a | b>= b$
所有变化后一定更优。

思路：发现两个数进行完操作后，
在都有1的位上不变，
在一个是1一个是0的位上，所有的1都到了一个数上。
001101010
010101000
变成：
000101000
011101010
发现只不过是将一个数的某些位上的1给了另一个数。所以将每个数拆成很多个1，可以计算出每一位一共有多少个1，每次一个数不停的取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;
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 mod = 998244353;
const int N = 200010;
int a[N], cnt[N];
int main() {
//  freopen("1.txt","r",stdin);
    freopen("s.in","r",stdin);
    freopen("s.out","w",stdout);
    int n = read(), mx = 0;
    for (int i=1; i<=n; ++i) {
        a[i] = read();
        for (int j=0; (1<<j)<=a[i]; ++j) {
            if ((1 << j) & a[i]) cnt[j] ++, mx = max(mx, j);
        }
    }
    LL Ans = 0;
    while (true) {
        LL x = 0, flag = 0;
        for (int i=0; i<=mx; ++i) {
            if (cnt[i]) x |= (1 << i), cnt[i] --, flag = 1;
        }
        if (!flag) break;
        Ans = (Ans + 1ll * x * x) % mod;    
    }
    cout << Ans % mod;
    return 0;
}

T3

暴力写了很长时间。。。
然后感觉好像轮廓线dp，记录上两行的状态，转移，然后发现空间开不下，时间也不对。空间$2^{m+m}$。
正解：其实不是轮廓线dp，直接状压dp，发现很多状态是一定不合法的。比如001100,001010这种就不合法，去掉这种，发现只剩下了406个，然后状态就很少了，可以转移了。

#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 mod = 1e9 + 7;
int ban[16], f[16][500][500];
vector <int> sta;
inline bool isLine(int a) {
    return !((a & (a << 1)) || (a & (a << 2)));
}
inline bool isTwoLines(int a,int b) {
    return !((a & b) || (a & (b << 1)) || (a & (b >> 1)));
}
inline bool isThreeLines(int a,int b,int c) {
    return !(a & c) && isTwoLines(b, c);
}
int main() {
    int n = read(), m = read(), k = read();
    for (int i=1; i<=k; ++i) {
        int x = read(), y = read();
        ban[x] |= (1 << (y - 1));
    }
    for (int i=0,lim=(1<<m)-1; i<=lim; ++i) 
        if (isLine(i)) sta.push_back(i);
    int maxS = sta.size();
    for (int i=0; i<maxS; ++i) 
        f[0][i][0] = 1;
    LL ans = 0;
    for (int i=1; i<=n; ++i) {
        for (int a=0; a<maxS; ++a) { // 当前行的状态 
            if (sta[a] & ban[i]) continue; 
            for (int b=0,lim=(i<=1?1:maxS); b<lim; ++b) { // i - 1行 
                if ((sta[b] & ban[i - 1]) || !isTwoLines(sta[a], sta[b])) continue;
                for (int c=0,lim2=(i<=2?1:maxS); c<lim2; ++c) { // i - 2行
                    if ((sta[c] & ban[i - 2]) || !isThreeLines(sta[a], sta[b], sta[c])) continue; 
                    int &ts = f[i][a][b];
                    f[i][a][b] = (f[i][a][b] + f[i - 1][b][c]) % mod;
                    ts = f[i][a][b];
                }
                if (i == n) ans = (ans + f[i][a][b]) % mod;
            }
        }
    }
    cout << ans;
    return 0;
}