在这里做一个小小的说明: 之前在QQ空间发了一篇立志贴, 但是很快补考就来了, 所以从昨天开始算, 一天一道regional题, 三天一套多校...
250pt
算法分析:
二分枚举结果是最好写的, 但是不是最优的. 但是我偏偏没有选择最好些的.
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
typedef long long ll;
ll stk[55];int vis[55];
bool flag;
ll work(vector<int> num){
int tp = 0;
memset(vis,0,sizeof(vis));
for(int i = 0; i < num.size(); i++) {
if(num[i] == 0) {
if(tp <= 1) continue;
else {
tp --;
if(stk[tp ] == -1 || stk[tp-1] == -1){
vis[tp - 1] = 1;
vis[tp] = 0;
}
else if(vis[tp] == 1 || vis[tp - 1] == 1) {
vis[tp-1] = 1;
vis[tp] = 0;
}
stk[tp-1] += stk[tp];
}
}
else {
stk[tp++] = num[i];
}
}
flag = vis[tp-1] || (stk[tp-1] == -1);
if(flag) stk[tp-1]++;
return stk[tp-1];
}
class
Suminator{
public : int findMissing(vector <int> p, int R){
int n = p.size(),s;
for(int i = 0; i<n; i++){
if(p[i] == -1) s = i;
}
p[s] = 0;
ll t = work(p);
if(t == R) return 0;
p[s] = -1;
t = work(p);
if(!flag) {
if(t == R) return 1;
else return -1;
}
else {
ll x = R - t;
if(x < 1) return - 1;
else return x;
}
}
};
500pt
算法分析:
一共就两个凸联通块,每个凸联通块一定是逐增不(下降,上升)的.
于是乎可以DP, DP[i][j][a][b]表示第i层,前j行都选取字母a的行数不上升/下降的总情况.
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
using namespace std;
typedef long long ll;
ll dp[55][55][2][2];
const int mod = (int)1e9+7;
class TwoConvexShapes{
public: int countWays(vector <string> num){
int n = num.size(), m = num[0].size();
for(int p = 0; p<2; p++){
for(int oo = 0; oo <2; oo++) {
char x = oo ? 'B' : 'W';
char y = oo ? 'W' : 'B';
for(int i = 0; i < n; i++){
for(int r = 0; r <= m; r++){
bool flag = 1;
for(int j = 0; j < m; j++)
if(j < r && num[i][j] == x || j >= r && num[i][j] == y )
flag = 0;
// if(!flag) cout<<i<<" "<<r<<endl;
if(!flag) continue;
for(int j = 0; j <= m; j++){
if(i==0) dp[i][r][oo][p] = 1;
else if(p && j >= r || !p && j <= r)
dp[i][r][oo][p] += dp[i-1][j][oo][p];
}
dp[i][r][oo][p] %= mod;
}}}}
//cout<< dp[n-1][0][0][0] <<" "<<dp[n-1][1][0][0]<<" "<<dp[n-1][2][0][0]<<endl;
ll ans = 0;
for(int i = 0; i <= m; i++)
for(int a = 0; a< 2; a++)
for(int b = 0; b < 2; b++)
ans += dp[n-1][i][a][b];
ans %= mod;
int sum = 0,w = 0, b = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
if(num[i][j] == 'W') w = 1;
else if(num[i][j] == 'B') b = 1;
sum = (!w + !b) * 3;
for(int u = 1; u < n; u++)
for(int oo = 0; oo < 2; oo++) {
bool flag = 1;
char x = oo ? 'B' : 'W';
char y = oo ? 'W' : 'B';
for(int i = 0; i < n; i++)
for(int j = 0; j< m; j++)
if(i < u && num[i][j] == x || i >= u && num[i][j] == y)
flag = 0;
sum += flag;
}
for(int r = 1; r < m; r++)
for(int oo = 0; oo < 2; oo++) {
bool flag = 1;
char x = oo ? 'B' : 'W';
char y = oo ? 'W' : 'B';
for(int i = 0; i < n; i++)
for(int j =0; j < m; j++)
if(j < r && num[i][j] == x || j >= r && num[i][j] == y)
flag = 0;
sum += flag;
}
// cout<< ans << " "<< sum<<endl;
return (ans - sum + mod) % mod;
}
};
posted on 2012-08-23 16:53
西月弦 阅读(307)
评论(0) 编辑 收藏 引用 所属分类:
解题报告