渣新:..: August 2014

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);
        }
    }
}

给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;
    }
};

SRM 618 div2 900

Google APAC 2015 University Graduates Test A

SRM 619 div2 950

SRM 620 div2 1000

SRM 621 div2 1000

SRM 622 div2 1000