这个题直接看了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我等渣新也是想了许久..
稿纸上写写画画后总结出第一种转移:
连续的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进制表示法
记忆话检查的办法收到了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
写出代码
..:
简单的位运算+一些特殊情况的判断:..
最最关键的地方其实是, 求出所有可能值之后, 先判断是否该值和无法确认好坏的段有交, 其次对每一个可能值计算最终显示值
如果全部一样, 那就是无歧义显示:..
我的代码复杂度是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
写出代码
..:
其中每个点有权值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个点的组件..
递归函数详见题解>.<..
写出代码
..:
求图中有>=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, 扫描方向不同罢了~~
写出代码
..:
题解中提到了线性无关, 空间的基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元素的子集, 看是否满足要求
排序后可以剪枝, 就是当发现已经不满足就没有必要继续枚举了
写出代码
..:
所有数字和大于数字积, 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;
}
};
Subscribe to:
Posts
(
Atom
)