策勒网站建设,dw软件是做什么用的,莱西做网站,祁东seo公司C 豆子
构造题
由构造公式知 第n级好豆子 第n-1级坏豆子^1
所以只需要构造一个豆子结构就行 第 i 级豆子 第 i 级豆子 第 i 级豆子 第 i 级豆子 第 i 级豆子 ^ 1 第i级豆子\begin{aligned} 第i级豆子 第i级豆子 \\ 第i级豆子 第i级豆子 \verb|^| 1 …C 豆子
构造题
由构造公式知 第n级好豆子 第n-1级坏豆子^1
所以只需要构造一个豆子结构就行 第 i 级豆子 第 i 级豆子 第 i 级豆子 第 i 级豆子 第 i 级豆子 ^ 1 第i级豆子\begin{aligned} 第i级豆子 第i级豆子 \\ 第i级豆子 第i级豆子 \verb|^| 1 \end{aligned} 第i级豆子第i级豆子第i级豆子第i级豆子第i级豆子^1
预处理构造一下输出就行
#includeiostream
using namespace std;
bool s[1100][1100];
bool d[6][6];
void init(int n)
{s[1][1] 1;for(int i2;in;i){int x (1(i-2));for(int j1;jx;j)for(int k1;kx;k){s[jx][k] s[j][k];s[j][kx] s[j][k];s[jx][kx] s[j][k]^1;}}for(int i3;i6;i)for(int j3;j6;j)d[i][j] 1;
}
void print(int x,int y,int u)
{for(int i0;i6;i){for(int j1;jy;j)for(int k0;k6;k){if((s[x][j]^u^d[i][k]))cout*;elsecout.;}coutendl;}
}
int main()
{int n;cinn;init(n);int d (1(n-1));for(int i1;id;i){print(i,d,n1^1);}return 0;
}D 矩阵
直接两层bfs就行
#includebits/stdc.h
using namespace std;
int dp[1010][1010][2];
int dr[] {-1,0,1,0,0,1,0,-1};
queuevectorintq;
string arr[1010];
int n,m;
void bfs(int x,int y,char f)
{memset(dp,0x3f,sizeof(dp)); dp[x][y][f-0] 0;q.push({x,y,f-0});while(!q.empty()){auto u q.front();q.pop();for(int i0;i4;i){int nx u[0] dr[i1];int ny u[1] dr[i1|1];int nf u[2]^1;if(nx0 nxn ny0 nym){int cost 1;if(arr[nx][ny]-0 ! nf)cost 2;if(dp[nx][ny][nf]dp[u[0]][u[1]][u[2]]cost){q.push({nx,ny,nf});dp[nx][ny][nf]dp[u[0]][u[1]][u[2]]cost;}}}}}int main()
{cinnm;for(int i0;in;i)cinarr[i];bfs(0,0,arr[0][0]);coutmin(dp[n-1][m-1][0],dp[n-1][m-1][1])endl;
}/*
dp大概率会卡这组数据
2 10
1111101010
0101011111
*/E 数数
由于数字不大直接dp
用dp[i][j]表示长度为i时前缀和为j的方案数显然只有 i ∣ j i|j i∣jj被i整除时才存在方案数
可以推出 d p [ i ] [ j ] { 0 , j m o d i ≠ 0 ∑ k j − m j d p [ i − 1 ] [ k ] , j m o d i 0 dp[i][j] \begin{cases} \ \ \ \ 0\ , j\ mod\ i \ne 0 \\ \sum\limits^{j}_{k j-m}dp[i-1][k] , j\ mod\ i0 \end{cases} dp[i][j]⎩ ⎨ ⎧ 0 kj−m∑jdp[i−1][k],j mod i0,j mod i0
这么遍历一次复杂度为 O ( n m l n ( n m ) ) O(nmln(nm)) O(nmln(nm)),由于dp中有很多0所以可以优化一下 ∑ k j − m j d p [ i − 1 ] [ k ] ∑ k j − m 1 i − 1 j i − 1 d p [ i − 1 ] [ k ∗ ( i − 1 ) ] \sum\limits^{j}_{k j-m}dp[i-1][k] \sum \limits^{\frac{j}{i-1}}_{k\frac{j-m1}{i-1}}dp[i-1][k*(i-1)] kj−m∑jdp[i−1][k]ki−1j−m1∑i−1jdp[i−1][k∗(i−1)]
那么复杂度就变成了 O ( n l n ( n m ) l n ( m ) ) O(nln(nm)ln(m)) O(nln(nm)ln(m))
#includebits/stdc.h
using namespace std;
using ll long long;
const ll mod 1e97;ll dp[6000000];
int main()
{int n,m;cinnm;for(int j1;jm;j)dp[j] 1;for(int i2;in;i){for(int ji*m;ji;j-i){dp[j] 0;for(int k j/(i-1)*(i-1);kmax(0,j-m);k-i-1)dp[j] (dp[j]dp[k])%mod;}}int ans 0;for(int in;in*m;in)ans (ansdp[i])%mod;coutansendl;
} F 打牌 直接大力出奇迹乱搞得了
通过阅读题目 而阿宁在手上有两张相同的牌第三张不同的牌时阿宁在相同的牌中等概率随机挑一张交给下家。其它情况阿宁也是等概率随机挑选。 分析会发现阿宁的行为是确定的。即如果此时没有人win阿宁就会把手中最多的牌发出去。所以在没有剪枝的情况下复杂度应该为 O ( 4 n ) O(4^n) O(4n)
说实话这游戏想长时间不赢其实很难的,阿宁的操作保证在多轮操作后他手上至少会有两种手牌所以说阿宁一直处于听牌的状态“只要能拿到那张牌……”“不好意思和”,
然后考虑如果其中一个人有三张的情况假设为aaa,另外两人就是bbc,ccb。如果aaa是阿宁上家阿宁就赢了。
下家(A)为aaa的时候此时 阿宁:bbc Aaaa B: ccb
阿宁打bA打a如果B不打b就赢了因此想要游戏继续下去就得打b因此就变成 阿宁:bbc Aaab B: cca
考虑大伙都有两张牌的情况会发现b手上至少存在一张能让阿宁赢的牌阿宁打出去的牌必然是a需要的牌阿宁手上有的牌ab都有(都可以用反证法证明)。用字母表示当前情况 阿宁:aab Abbc/cca B: cca/bbc
第一种情况{aab,cca,bbc}:
只有一种打法能让游戏继续下去那就是阿宁打出AA打出cB打出a,此时会变成{aab,abb,ccc}情况。根据上面的分析此时阿宁必赢
第二种情况{aab,cca,bbc}
阿宁打出a,B为了阿宁不赢得打出b,A为了B不赢得打出c此时变成{bba,aac,ccb}变成了必赢态
分析了一大轮就会发现在有限步内必有人会赢而且这个有限步甚至不会超过5步。
所以这题直接暴力dfs就完事了甚至不用剪枝。乱搞就行了。
#includebits/stdc.h
#define ll long long
using namespace std;
const ll mod 1e97;
ll sp[3][3];
ll now[3][3];
mapchar,intmp;
ll qpow(ll a,ll b)
{ll ret 1;while(b){if(b1) ret ret*a%mod;a a*a%mod;b1;}return ret;
}
ll dfs(int n)
{for(int i0;i3;i)if(sp[i][0]*sp[i][1]*sp[i][2])return i0;if(!n)return 0;ll ret 0;int mx 0;if(sp[0][1]sp[0][mx]) mx 1;if(sp[0][2]sp[0][mx]) mx 2;for(int i0;i3;i){if(!sp[1][i])continue;for(int j0;j3;j){if(!sp[2][j])continue;ll p 1ll*sp[1][i]*sp[2][j]*qpow(9,mod-2)%mod;sp[0][mx]--;sp[1][mx];sp[1][i]--;sp[2][i];sp[2][j]--;sp[0][j];ret (retdfs(n-1)*p%mod)%mod;sp[0][mx];sp[1][mx]--;sp[1][i];sp[2][i]--;sp[2][j];sp[0][j]--;}}return ret;
}
int main()
{mp[w] 0;mp[i] 1;mp[n] 2;int n;cinn;for(int i0;i3;i)for(int j0;j3;j){char c;cinc;sp[i][mp[c]];}ll ans dfs(n);coutansendl;
}
