codeforces contest 255

（ACM）动态规划 （ACM）数学----博弈论 （ACM）二分 （ACM）推公式

255C Almost Arithmetical Progression（dp）

题意

• 给出一个数组 $1<=n<=4000$
• 找出满足序列是 $[a,b,a,b,...]$ 的最长子序列
• 输出最长子序列的长度

题解

• 题解一：
  
  • $d[i][j]$ 表示 $i$ 是序列最后一个数的下标， $j$ 是倒二个
  • 那么对于每个 $i$ ，枚举 $j$ 便可以了。$d[i][j]=d[j][last]+1$，其中 $last$ 满足距离 $i$ 最近并且 $a[i]==a[last]$
• 题解二：
  
  • 比赛时想了很久，想出了奇怪的做法。
  • 预处理所有数都一样的情况。
  • 离散化。
  • $res[i][j]$ 表示序列第一个数离散化后坐标是 $i$，第二个数是 $j$
  • $res[i][j][0]$ 表示第一个数出现的次数
  • $res[i][j][1]$ 表示第二个数出现的次数
  • 对于每个数，$O(n)$ 地去找与之配对的第一个数或者第二个数。
  • 作为第一个数的时候，第一个数与第二个数出现次数一样就可以更新。
  • 作为第二个数的时候，第一个数比第二个数出现次数多一就可以更新。

代码

///solve 1
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=4005;
int a[N],d[N][N];
int main() {
    int n;
    while(~scanf("%d",&n)) {
        ///init
        memset(d,0,sizeof(d));
        ///solve
        int ans=1;
        for(int i=1;i<=n;++i) {
            scanf("%d",a+i);
            for(int j=0,last=0;j<i;++j) {
                d[i][j]=max(d[i][j],d[j][last]+1);
                if(a[j]==a[i]) last=j;
                ans=max(ans,d[i][j]);
            }
        }
        ///print
        printf("%d\n",ans);
    }
    return 0;
}

///solve 2
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <string>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define de(x) cout << #x << "=" << x << endl
const int N=4005;
int a[N],b[N],res[N][N][2];
int main() {
    int n;
    while(~scanf("%d",&n)) {
        ///init
        memset(res,0,sizeof(res));
        ///read
        for(int i=1;i<=n;++i) {
            scanf("%d",a+i);
            b[i]=a[i];
        }
        ///sort
        sort(a+1,a+1+n);
        ///
        int ans=1;
        a[n+1]=a[n]+1;a[0]=a[1];
        int now=0;
        for(int i=1;i<=n+1;++i) {
            if(a[i]==a[i-1]) ++now;
            else {
                ans=max(ans,now);
                now=1;
            }
        }
        ///get a
        int m=0;a[++m]=a[1];
        for(int i=2;i<=n;++i) {
            if(a[i]!=a[i-1]) a[++m]=a[i];
        }
        ///solve
        for(int i=1;i<=n;++i) {
            int p=lower_bound(a+1,a+1+m,b[i])-a;
            for(int j=1;j<=m;++j) {
                if(j==p) continue;
                if(res[p][j][0]==res[p][j][1]) ++res[p][j][0];
                if(res[j][p][1]==res[j][p][0]-1) ++res[j][p][1];
            }
        }
        ///print
        for(int i=1;i<=m;++i) {
            for(int j=1;j<=m;++j) {
                ans=max(ans,res[i][j][0]+res[i][j][1]);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

255D Furlo and Rublo and Game（二分+推公式）

题意

题解

• 二分答案
• 对于每个答案，推一下有多少空格被染色

代码

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <string>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define de(x) cout << #x << "=" << x << endl
ll n,x,y,c;
ll ca(ll x,ll y,ll mid) {
    ll t=mid-x+1;if(t<0) t=0;
    ll ans=-t*t;
    t=mid-n-x+y;if(t<0) t=0;
    ans=ans+(1+t)*t/2;
    return ans;
}
ll calc(ll mid) {
    ll ans=1+mid*(1+mid)*2;
    ans=ans+ca(x,y,mid);
    ans=ans+ca(y,n+1-x,mid);
    ans=ans+ca(n+1-y,x,mid);
    ans=ans+ca(n+1-x,n+1-y,mid);
    return ans;
}
bool check(ll mid) {
    return calc(mid)>=c;
}
int main() {
    while(~scanf("%I64d%I64d%I64d%I64d",&n,&x,&y,&c)) {
        ll l=0,r=3e9,ans=0;
        while(l<=r) {
            ll mid=(l+r)>>1;
            if(check(mid)) {
                ans=mid;
                r=mid-1;
            } else {
                l=mid+1;
            }
        }
        printf("%I64d\n",ans);
    }
    return 0;
}

255E Furlo and Rublo and Game（博弈论）

题意

• n堆石子 $(1 ≤ n ≤ 77777)$，石子个数超过int范围
• 如果当前石子个数 $x$，可以取走某些石子，使得剩下 $y$。$x、y$ 满足 $(0 ≤ y < x，x^{1/4}≤ y ≤ x^{1/2})$

题解

• 对于小的数据打表，发现sg值很少，并且都是一大块一大块的。
• 大数据打表会爆栈，所以就手动打表了...
• 非常无聊的题...

代码

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <string>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define de(x) cout << #x << "=" << x << endl
int sg(ll x) {
    if(0<=x&&x<=3) return 0;
    if(4<=x&&x<=15) return 1;
    if(16<=x&&x<=81) return 2;
    if(82<=x&&x<=6723) return 0;
    if(6724<=x&&x<=50625) return 3;
    if(50626<=x&&x<=2562991875) return 1;
    return 2;
}
int main() {
    int n;
    while(~scanf("%d",&n)) {
        ll ans=0;
        for(int i=1;i<=n;++i) {
            ll x;scanf("%I64d",&x);
            ans^=sg(x);
        }
        if(ans) puts("Furlo");
        else puts("Rublo");
    }
    return 0;
}