URAL 1346 Intervals of Monotonicity

这个题直接看了Nocow上的代码..
很简单的DP解法..因为之前也遇到过类似的题目没有A掉, 抄完代码也没深入去想就不了了之..
这样是不对的..于是在这题的DP解法上好好想了想..

分析
..:
先说状态转移:

d[x][w] - x位置的数被分为单增(w=1)或分为单减(w=0)时的最小段数
d[x][w]=d[x-1][w], if no turning
            =min(d[x-1][0]+d[x-1][1])+1, if a turning encountered

伪代码
..:
d[a][0]=1;
d[b][1]=1;
for i from a to b:
  if F[i]>F[i-1]:
    d[i][0]=min(d[i-1][0], d[i-1][1])+1;
  else
    d[i][0]=d[i-1][0]
  if F[i]<F[i-1]:
    d[i][1]=min(d[i-1][0], d[i-1][1])+2;
  else
    d[i][1]=d[i-1][1]

答案就是min(d[b][0], d[b][1])

什么乱起八糟的呐这是..
对区间上的每一个拐点, 我们可以把他归为之前的结尾, 或之后的起点, 也就是说..
1 2 3 4 5 4 3
F[i]=4<F[i-1]=5, 拐点来了..那么i-1既可以是起点, 又可以是终点, 如下:
1 2 3 4 | 5 4 3
1 2 3 4 5 | 4 3

完了..

URAL 2018 The Debut Album

题意呐就是给一个n位的二进制数, 要求:
连续的0不能超过a个.
连续的1不能超过b个.
问这种二进制数共多少种?
1<=n<=50000
1<=a, b<=300

分析
..:
就是这样简单的DP我等渣新也是想了许久..
稿纸上写写画画后总结出第一种转移:

 d[x][k][w] - 在x位置时已有连续k个w时的种数
那么
d[x][k][w]=d[x+1][1][1-w]
d[x][k][w]+=d[x+1][k+1][w], if k<a when w is 0, or k<b when w is 1
时间复杂度应该是O(nab)?..
但是..空间严重超出64MB..

于是继续埋头观察稿纸, 研究规律..良久..咦!..
出现了:
d[x][w] - 当前位置x是w时的种数
那么
d[x][w]=d[x][w]+d[x+k][1-w], for k from 1 to a when w is 0, or from 1 to b when w is 1
时间复杂度同上(应该..)

写出代码
..:
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007

int d[50001][2];
int ab[2];
int n;
inline int dodp(int x, int w) {
  if (x==n) {
    return 1;
  } else {
    int& r=d[x][w];
    if (r==-1) {
      r=0;
      for (int i=1; i<=ab[w]; i++) if (x+i<=n) {
        r=(r+dodp(x+i, 1-w))%mod;
      }
    }
    return r;
  }
}
int main(void) {
  scanf("%d%d%d", &n, &ab[0], &ab[1]);
  memset(d, 0xff, sizeof d);
  printf("%d\n", (dodp(0, 0)+
    dodp(0, 1))%mod);
}

SRM 633 div2 1000

又是G家猥琐的题
我采用了暴力搜索的办法, 当然要根据以下性质剪枝:
对任意两个整数x, y
x*y=gcd(x, y)*lcm(x, y)
利用这个剪枝, 如果所有的连通组件都能访问到就是有解了
代码中第一次DFS找出所有连通组件, 第二次则是尝试访问所有点

写出代码
..:
#include <bits/stdc++.h>
using namespace std;
struct edg {
    int n, g, l;
    edg(int _n, int _g, int _l) { n=_n, g=_g, l=_l; }
};
struct cmp {
    int s, h;
    cmp(int _s, int _h) { s=_s, h=_h; }
};
typedef vector<edg> ve;
typedef vector<cmp> vc;
#define pb push_back
#define ret return

int f, t;
int w[501];
int v[501];
ve  g[501];
vc  c;
inline int dfs1(int x) {
    v[x]=1;
    int r=1;
    for (edg e : g[x]) if (!v[e.n]) r+=dfs1(e.n);
    ret r;
}
inline int dfs2(int x, int c, int p) {
    v[x]=1;
    w[x]=c;
    int r=1;
    for (edg e : g[x]) if (e.n!=p) {
        int p=e.g*e.l;
        if (v[e.n]) {
            if (c*w[e.n]!=p || __gcd(c, w[e.n])!=e.g) ret 0;
        } else {
            if (p%c==0 && __gcd(c, p/c)==e.g)
                r+=dfs2(e.n, p/c, x);
            else
                ret 0;
        }
    }
    ret r;
}
class GCDLCMEasy {
public:
    string possible(int n, vector <int> A, vector <int> B, vector <int> G, vector <int> L) {
        for (int i=0; i<A.size(); i++) {
            g[A[i]].pb(edg(B[i], G[i], L[i]));
            g[B[i]].pb(edg(A[i], G[i], L[i]));
        }
        for (int i=0; i<n; i++) if (!v[i]) c.pb(cmp(i, dfs1(i)));
        memset(v, 0, sizeof v);
        f=1;
        for ( ; f && t<c.size(); t++) if (!g[c[t].s].empty()) {
            f=0;
            edg& e=g[c[t].s][0];
            int  p=e.g*e.l;
            for (int i=1; i<=p; i++) if (p%i==0 && __gcd(i, p/i)==e.g) {
                w[c[t].s]=i;
                if (dfs2(c[t].s, i, -1)==c[t].h) {
                    f=1;
                    break;
                } else {
                    memset(v, 0, sizeof v);
                }
            }
        }
        ret f ? "Solution exists" :
                "Solution does not exist";
    }
};

SRM 618 div2 900

一个nXn棋盘, 每行有一个棋子, 若任意每对棋子不同行同列该棋盘为和平棋盘
现给出两个和平棋盘, 问是否能经过K步操作将棋盘1转化为棋盘2
1<=n<=8, K未知

观察
..:
一道非常裸的搜索题, 外加一点一点记忆化的思想, 细节见代码
记忆话检查的办法收到了SRM628某题的启发, 使用了8进制表示法

写出代码
..:
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vin;
typedef map<int, int> mii;

int n, f;
mii v;
vin g, t;
inline void dodo() {
    int k=0, i;
    for (i=0; i<n; i++) k+=g[i]*pow(8, i);
    if (v[k])
        return;
    v[k]=1;
    for (i=0; i<n; i++) if (g[i]!=t[i])
        break;
    if (i==n) {
        f=1;
        return;
    }
    int t;
    for (int i=1; !f && i<n; i++)
        for (int j=0; !f && j<i; j++) if (g[j]>g[i]) {
            t=g[i], g[i]=g[j], g[j]=t;
            dodo();
            t=g[i], g[i]=g[j], g[j]=t;
        }
}
class MovingRooksDiv2 {
public:
 string move(vector <int> Y1, vector <int> Y2) {
        n=Y1.size();
        g=Y1;
        t=Y2;
        dodo();
        return f ? "Possible" :
                   "Impossible";
    }
};

Google APAC 2015 University Graduates Test A

这道题非常无节操:..
简单的位运算+一些特殊情况的判断:..
最最关键的地方其实是, 求出所有可能值之后, 先判断是否该值和无法确认好坏的段有交, 其次对每一个可能值计算最终显示值
如果全部一样, 那就是无歧义显示:..
我的代码复杂度是n

写出代码

..:
#include <bits/stdc++.h>
using namespace std;
struct res {
    int w, g, x;
};
typedef vector<int> vi;
typedef vector<res> vr;
#define pb push_back
#define all(c) (c).begin(), (c).end()

int T;
int d[10]={126, 48, 109, 121, 51, 91, 95, 112, 127, 123};
int main(void) {
    scanf("%d", &T);
    for (int t=1; t<=T; t++) {
        vi m[101];
        vr r;
        int n, g, x, c, f, l[101];
        char w[8];
        scanf("%d", &n);
        for (int i=0; i<n; i++) {
            c=0;
            scanf("%s", w);
            for (int j=6; j>=0; j--) if (w[j]=='1') c|=1<<(6-j);     
            for (int j=0; j<10; j++) if ((d[j]|c)==d[j]) m[i].pb(j); 
            l[i]=c;                                                  
        }
        for (int i=0; i<m[0].size(); i++) {                         
            f=m[0][i];
            g=(~l[0])&d[f];                                        
            x=l[0]&d[f];
            c=(f+9)%10;                                           
            for (int j=1; j<n; j++, c=(c+9)%10) {
                if (!binary_search(all(m[j]), c)) {
                    goto next;
                } else {
                    g|=(~l[j])&d[c];                                
                    x|=l[j]&d[c];
                }
            }
            for (int k=0; k<n; k++) if (g&l[k])
                goto next;
            r.pb((res){c, g, x});
next:;
        }
        if (r.size()) {
            f=1;
            for (int i=0; f && i<r.size(); i++) if (d[r[i].w]&(~(r[i].g|r[i].x)))
                f=0;
            if (f) {
                c=d[r[0].w]&(~r[0].g)&r[0].x;
                for (int i=1; f && i<r.size(); i++) if ((d[r[i].w]&(~r[i].g)&r[i].x)!=c)
                    f=0;
                if (f) {
                    printf("Case #%d: ", t);
                    cout<<bitset<7>(c)<<endl;
                } else {
                    printf("Case #%d: ERROR!\n", t);
                }
            } else {
                printf("Case #%d: ERROR!\n", t);
            }
        } else {
            printf("Case #%d: ERROR!\n", t);
        }
    }
}


SRM 619 div2 950

给n个点的完全图, 求诱导子图(可空可全图), 最大化利益P, 2<=n<=50
其中每个点有权值Vi, 每条边有权值Eij
若点在子图中则利益P-Vi
若边在子图中则利益P+Eij, 否则不在, 利益P-Eij(若该边有1个节点在子图中则对利益无影响)

举例
..:
点权值{2, 2}
边权值{{0, 1}, {1, 0}}
那么最大P就是空子图, P=-1

观察
..:
初始利益是-S(E)
对任一节点i, 若选入则增加-Vi+S(Eij)利益, S(Eij)是与i相连所有边权和
这样想是不会出现重复计算的, 即每个点是否选入不相干
因为对任意边, 选一个节点增加E, 再选一个又增加E

写出代码
..:
#include <bits/stdc++.h>
using namespace std;

int n, s, r;
class EmployManager {
public:
    int maximumEarnings(vector<int> v, vector<string> e) {
        n=v.size();
        for (int i=0; i<n; i++)
            for (int j=i+1; j<n; j++)
                r-=e[i][j]-'0';
        for (int i=0; i<n; i++) {
            s=0;
            for (int j=0; j<n; j++) s+=e[i][j]-'0';
            if (s-v[i]>0)
                r+=s-v[i];
        }
        return r;
    }
};

SRM 620 div2 1000

给n个点(0, 1, 2, ..., n-1), 每对点之间有边的概率是p/1000, 每对点之间至多一条边
求图中有>=4个点的连通组件的概率

这题想了一天, 又向题解屈服了QAQ..
题解中结合了动态规划和对立事件..
想到了用动态规划来解, 但是状态很简单..
D[i], i个节点组成的图满足题意的概率..
那么递推公式就是D[i+1]=D[i]*P..P不知道如何计算..
也想到了对立事件, 即求图中仅有<4个点组件的概率P`, 那么答案就是1-P`..
但是没有结合二者深入思考..弱!..

观察1
..:
<4个点的组件只有四种形式..
O
O-O
O-O-O
O---O
 \ /
  O
..:
当要加入一个新节点, 会产生以下变化..
O     -> O-O
O-O   -> O-O-O or O---O
                   \ /
                    O
O-O-O -> O-O-O-O or O-O---O or ...
                       \ /
                        O
O---O -> ...
 \ /
  O
..:
观察发现..变化的是组成连通组件的点个数, 所以我们按节点个数来建立状态..

观察2
..:
D[a][b][c]
当前图中有a个1节点组件, b个2节点组件, c个3节点组件的概率..
f(r, a, b, c)
递归函数, 还要加入r个点, 状态是D[a][b][c]的概率..
f(n, 0, 0, 0)
我们的问题啦..
f(0, a, b, c)=1.0
终止条件, 这时候整个图就是a+b+c, 只有<4个点的组件..
递归函数详见题解>.<..

写出代码
..:
#include <bits/stdc++.h>
using namespace std;

bool   v[51][51][51];
double d[51][51][51];
double p;
inline double D(int R, int a, int b, int c) {
#define X 1-p
#define O p
    if (!v[a][b][c]) {
        v[a][b][c]=1;
        double r=.0;
        if (!R) {
            r=1.0;
        } else {
         r+=pow(X, a+2*b+3*c)*D(R-1, a+1, b, c);
         if (a>0) r+=pow(X, 2*b+3*c)*a*O*pow(X, a-1)*D(R-1, a-1, b+1, c);
         if (a>1) r+=pow(X, 2*b+3*c)*a*(a-1)/2*O*O*pow(X, a-2)*D(R-1, a-2, b, c+1);
         if (b>0) r+=pow(X, a+3*c)*2*b*O*pow(X, 2*b-1)*D(R-1, a, b-1, c+1),
                  r+=pow(X, a+3*c)*b*O*O*pow(X, 2*b-2)*D(R-1, a, b-1, c+1);
        }
        d[a][b][c]=r;
    }
    return d[a][b][c];
#undef X
#undef O
}
class RandomGraph {
public:
    double probability(int n, int p) {
        ::p=p/1000.0;
        return 1-D(n, 0, 0, 0);
    }
};

SRM 621 div2 1000

给一组数, 求异或运算下组成数组的基的元素个数, 1<=n<=50
题解中提到了线性无关, 空间的基QAQ

观察1
..:
所谓``异或运算下''就是所有元素由基中元素的异或产生
注意异或属于模2运算, 即对某数异或的结果只有异或奇数次和异或偶数次两种

举例
..:
若基是{1, 2}, 那么可产生所有元素是{1, 2, 3}
..:
若给出的是{1, 2, 3, 4, 5}
转为01表示
0001
0010
0011
0100
0101
立即使用线性代数中办法
设i从第一行开始, 对i行逐位扫描, i行后的每一行如果同位为1, 就异或, 1<=i<n
..:
其实就是化简矩阵求出线性无关向量的办法, 只不过这里是异或且只异或一次
..:
逐位扫描可以用__builtin_ffs, 也可以用__builtin__clz, 扫描方向不同罢了~~

写出代码
..:
#include <bits/stdc++.h>
using namespace std;

int n, r;
inline void dodo(vector<int>& c, int x) {
    for (int i=x+1; i<n; i++) if (c[i]&(1<<__builtin_ffs(c[x])-1))
        c[i]^=c[x];
}
class MixingColors {
public:
    int minColors(vector <int> c) {
        n=c.size();
        for (int i=0; i<n; i++) if (c[i]) dodo(c, i);
        for (int i=0; i<n; i++) if (c[i]) r++;
        return r;
    }
};

SRM 622 div2 1000

给一有重复数字集合, 求满足以下性质的所有子集(可全集不可空集):
所有数字和大于数字积, 1<=n<=1000

观察1
..:
若xy<x+y则xy-x-y<0
即xy-x-y+1<1即(x-1)(y-1)<1, 可见x, y中至少有1
..:
若xyz<x+y+z则xyz-x-y-z<0
即xyz-xy-yz-zx+x+y+z-1+xy+yz+xz-2x-2y-2z+1<0
也(x-1)(y-1)(z-1)+(x-1)(y-1)+(y-1)(z-1)+(x-1)(z-1)<2, 可见x, y, z中至少有1
..:
猜测推广至n

观察2
..:
根据观察1可见复杂度并不是n的全子集, 至于是什么不会证QAQ:..

所以
..:
先求出1的个数, 然后枚举非1元素的子集, 看是否满足要求
排序后可以剪枝, 就是当发现已经不满足就没有必要继续枚举了

写出代码
..:
#include <bits/stdc++.h>
using namespace std;

int n, o, r, t;
int v[1001];
int m[1001];
int s[1001];
inline void dodo(int x, int c) {
    int a=0, b=1;
    for (int i=0; i<c; i++) a+=s[i], b*=s[i];
    if (b-a<=o)
        r+=o-(b-a);
    else
        return;
    for (int i=x; i<t; i++) if (v[i]) {
        s[c]=m[i];
        v[i]--;
        dodo(i, c+1);
        v[i]++;
    }
}
inline void push(int x) {
    for (int i=0; i<t; i++) if (m[i]==x) {
        v[i]++;
        return;
    }
    m[t]=x;
    v[t]++;
    t++;
}
class Subsets {
public:
    int findSubset(vector<int> N) {
        n=N.size();
        sort(N.begin(), N.end());
        for ( ; N[o]==1 && o<n; o++) ;
        for (int i=o; i<n; i++)
            push(N[i]);
        dodo(0, 0);
        printf("%d %d\n", n, o);
        return r;
    }
};