徐州网络赛2018

网络赛的题比赛应该不会出了吧 嗯......

【记忆化搜索求PN态】 BE, GE or NE

• 题意：三个操作，增加，减少，加负号。一个人要让该数字>=r,一个人要让该数字小于等于l。
• 很明显对于先手来说肯定是让分数最高最优，对于后手来说肯定是让分数最低最优。我们考虑所有的方案，肯定是 3^n，所以我们可以记忆化搜索， 一共只有 1000*200 种状态， 所以一定是可以算出来的
  一个点为必胜态，当且仅当他的后继 有一个必败态
  一个点为必败态，当且仅当他所有的后继 都是必胜态
  考虑这道题， 如果第一个人可以赢，他不会选择平， 更不会选择输
  对于第二个人同理

#include 
    
     using namespace std;#define ll long longconst int maxn=1005;int down,up,s,n;int a[maxn],b[maxn],c[maxn];int dp[maxn][305];int high,low;map
     
      mp;int dfs(int pos,int now){    if(pos==n+1){        if(now>=high){            return 2;        }        else if(now>low) return 1;        else return 0;    }    if(dp[pos][mp[now]]!=-1) return dp[pos][mp[now]];    if(pos%2==1){        int op=0;        if(a[pos]){            op=max(op,dfs(pos+1,min(now+a[pos],up)));        }        if(b[pos]){            op=max(op,dfs(pos+1,max(now+b[pos],down)));        }        if(c[pos]){            op=max(op,dfs(pos+1,-now));        }        return dp[pos][mp[now]]=op;    }    else{        int op=1e9;        if(a[pos]){            op=min(op,dfs(pos+1,min(now+a[pos],up)));        }        if(b[pos]){            op=min(op,dfs(pos+1,max(now+b[pos],down)));        }        if(c[pos]){            op=min(op,dfs(pos+1,-now));        }        return dp[pos][mp[now]]=op;    }}int main() {    int tol=0;mp.clear();    for (int i = -100; i <=100 ; ++i) {        mp[i]=++tol;    }    down=-100,up=100;    memset(dp,-1,sizeof(dp));    scanf("%d%d%d%d",&n,&s,&high,&low);    for (int j = 1; j <=n; ++j) {        scanf("%d%d%d",&a[j],&b[j],&c[j]);        b[j]=-b[j];    }    int op=dfs(1,s);    if(op==2){        puts("Good Ending");    }    else if(op==1){        puts("Normal Ending");    }    else puts("Bad Ending");    return 0;}
     
    

记忆化搜索：算法上依然是搜索的流程，但是搜索到的一些解用动态规划的那种思想和模式作一些保存。

一般说来，动态规划总要遍历所有的状态，而搜索可以排除一些无效状态。

更重要的是搜索还可以剪枝，可能剪去大量不必要的状态，因此在空间开销上往往比动态规划要低很多。

记忆化算法在求解的时候还是按着自顶向下的顺序，但是每求解一个状态，就将它的解保存下来，

以后再次遇到这个状态的时候，就不必重新求解了。

这种方法综合了搜索和动态规划两方面的优点，因而还是很有实用价值的

【暴力求期望+题意】Cacti Lottery

这题真的题意杀.....

挺难读懂的，123代表已经知道的数，*代表知道是那些数但是不知道具体的，#代表未知的数。然后求期望。

#include 
    
     using namespace std;typedef long long ll;int num[25] = { 0,0,0,0,0,0,10000,36,720,360,80,252,108,72,54,180,72,180,119,36,360,1080,144,1800,3600};char mp[5][5];int vis[10];int cnt = 0, cnt1 = 0, cnt2 = 0;char mp2[10];int fial[10];int idx = 0;double allans = 0;int ans[10];int A(int n, int m){    int res = 1;    for (int i = 1; i <= m; i++) {        res *= (n - i + 1);    }    return res;}void check1(){    ans[0] += num[fial[0] + fial[1] + fial[2]];    ans[1] += num[fial[3] + fial[4] + fial[5]];    ans[2] += num[fial[6] + fial[7] + fial[8]];    ans[3] += num[fial[0] + fial[3] + fial[6]];    ans[4] += num[fial[1] + fial[4] + fial[7]];    ans[5] += num[fial[2] + fial[5] + fial[8]];    ans[6] += num[fial[0] + fial[4] + fial[8]];    ans[7] += num[fial[2] + fial[4] + fial[6]];}void dfs2(int num){    if (num == 9)    {        check1();        return;    }    if (fial[num] != 0) dfs2(num + 1);    else {        for (int i = 1; i <= 9; i++)        {            if (vis[i])continue;            vis[i] = 1;            fial[num] = i;            dfs2(num + 1);            fial[num] = 0;            vis[i] = 0;        }    }}void dfs(int num){    if (num == 9)    {        memset(ans, 0, sizeof(ans));        dfs2(0);        int maxx = 0;        for (int i = 0; i < 8; i++)        {            maxx = max(maxx, ans[i]);        }        allans += maxx / (A(cnt2,cnt2)*1.0);        return;    }    if (mp2[num] == '#') { dfs(num + 1); }    else if (mp2[num] != '*') { fial[num] = mp2[num] - '0'; dfs(num + 1); }    else {        for (int i = 1; i <= 9; i++)        {            if (vis[i]) continue;            vis[i] = 1;            fial[num] = i;            dfs(num + 1);            vis[i] = 0;        }    }}int main(){    int T;    scanf("%d", &T);    while (T--)    {        memset(vis, 0, sizeof(vis));        memset(fial, 0, sizeof(fial));        memset(mp2, 0, sizeof(mp2));        int p = 0;        cnt1 = 0;        cnt2 = cnt = 0;        idx = 0;        allans = 0;        for (int i = 1; i <= 3; i++)        {            scanf("%s", mp[i]);            int len = strlen(mp[i]);            for (int j = 0; j
     
      = '0')                {                    int k = mp[i][j] - '0';                    vis[k] = 1;                    cnt1++;                }                if (mp[i][j] == '*')                    cnt++;                mp2[idx++] = mp[i][j];            }        }        cnt2 = 9 - cnt1 - cnt;        dfs(0);        int k = A(9 - cnt1, cnt);        double tt = allans / k * 1.0;        printf("%.6lf\n", tt);    }    return 0;}
     
    

【set+模拟】 Trace

当初没做出来，用set维护就可以解决问题。

也可以说是思维题吧

#include 
    
     using namespace std;#define ll long longvector
     
      vector1;vector
      
       vector2;ll solve(vector
       
        v1){    ll res=0;    set
        
         set1;    int len=v1.size();    for (int i = len-1; i >=0 ; --i) {        set
         
          ::iterator it=set1.lower_bound(v1[i]); if(it==set1.begin()){ res+=v1[i]; } else{ it--; res+=v1[i]-*it; } set1.insert(v1[i]); } return res;}int main(){ int n,x,y; scanf("%d",&n); for (int i = 1; i <=n; ++i) { scanf("%d%d",&x,&y); vector1.push_back(x); vector2.push_back(y); } printf("%lld\n",solve(vector1)+solve(vector2));}