Ayi

953

Ayi
1小时前


#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 210 * 2;
const int INF = 0x3f3f3f3f;
int a[N * 2];
int f[N * 2][N * 2];//最小代价
int g[N * 2][N * 2];//最大代价
int s[N * 2];

int n;

int main() {

cin >> n;
memset(f,INF,sizeof f);
memset(g,-INF,sizeof g);
for (int i = 1 ; i <= 2 * n ; i ++ ) {
cin >> a[i];
a[n + i] = a[i];
s[i] = s[n + i] = s[i - 1] + a[i];
f[i][i] = 0 , g[i][i] = 0;
}

for (int len = 2 ; len <= n ; len ++ ) {
for (int l = 1 ; l + len - 1 <= 2 * n ; l ++ ) {
int r = l + len - 1;
for (int k = l ; k < r ; k ++ ) {
f[l][r] = min(f[l][r] , f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
g[l][r] = max(g[l][r] , g[l][k] + g[k + 1][r] + s[r] - s[l - 1]);
}
}
}
int mi = INF , mx = -INF;
for (int i = 1 ; i <= n  ; i ++ ) {
mi = min(mi , f[i][i + n - 1]);
mx = max(mx , g[i][i + n - 1]);
}

printf("%d\n" , mi);
printf("%d\n",mx);

return 0;
}



Ayi
7小时前
#include <bits/stdc++.h>

using namespace std;

const int N = 55, mod = 1e9 + 7;

int n, m;
char str[N];
int f[N][N];
int ne[N];

int main() {
cin >> n >> str + 1;
m = strlen(str + 1);

for (int i = 2, j = 0; i <= m; ++ i) {
while (j && str[i] != str[j + 1]) j = ne[j];
if (str[i] == str[j + 1]) ++ j;
ne[i] = j;
}

f[0][0] = 1;

for (int i = 0; i < n; ++ i)
for (int j = 0; j < m && i - j + 1 > 0; ++ j)
for (char k = 'a'; k <= 'z'; ++ k) {
int u = j;
while (u && k != str[u + 1]) u = ne[u];
if (k == str[u + 1]) ++ u;
if (u < m)
f[i + 1][u] = (f[i + 1][u] + f[i][j]) % mod;
}

int res = 0;
for (int i = 0; i < m; ++ i) res = (res + f[n][i]) % mod;

cout << res << "\n";

return 0;
}



Ayi
8小时前
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 1e5 + 10;
int f[N];
int main()
{
int n;
cin >> n;
int maxx = -0x3f3f;
for(int i = 1,x,s ; i <= n ; i++)
{
cin >> x;
maxx = i > 2 ? max(f[i-3] - s , maxx) : max(maxx, 0 - x);
f[i] = i > 1 ? max(f[i-1] , x + maxx) : f[i-1];
s = x ;
}
cout << f[n] << endl;
}



Ayi
10小时前
#include<bits/stdc++.h>
using namespace std;
const double eps=1e-8;
int t,n,m,lines[20][20],lowunbit[1<<20],dp[1<<20];  //lowunbit就是题解中的x
double x[20],y[20];
void equation(double &x,double &y,double a1,double b1,double c1,double a2,double b2,double c2){ //解方程
y=(a1*c2-a2*c1)/(a1*b2-a2*b1);
x=(c1-b1*y)/a1;
}
int main(){
for(int i=0;i<(1<<18);i++){ //预处理lowunbit
int j=1;
for(;j<=18 && i&(1<<(j-1));j++);
lowunbit[i]=j;
}
scanf("%d",&t);
while(t--){
memset(lines,0,sizeof(lines));  //各种初始化
memset(dp,0x3f,sizeof(dp));
dp[0]=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%lf%lf",x+i,y+i);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){  //处理所有抛物线
if(fabs(x[i]-x[j])<eps) continue;   //x坐标相同，不可能有解
double a,b;
equation(a,b,x[i]*x[i],x[i],y[i],x[j]*x[j],x[j],y[j]);
if(a>-eps) continue;    //解出a和b
for(int k=1;k<=n;k++)
if(fabs(a*x[k]*x[k]+b*x[k]-y[k])<eps) lines[i][j]|=(1<<(k-1));
}
for(int i=0;i<(1<<n);i++){  //重点！状压开始！
int j=lowunbit[i];  //必须经过lowunbit这个点
dp[i|(1<<(j-1))]=min(dp[i|(1<<(j-1))],dp[i]+1); //单独转移
for(int k=1;k<=n;k++) dp[i|lines[j][k]]=min(dp[i|lines[j][k]],dp[i]+1); //所有经过lowunbit的抛物线
}
printf("%d\n",dp[(1<<n)-1]);    //答案
}
}



Ayi
3天前

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 10, M = 1 << 10;

int n, m;
int g[1010];
int f[2][M][M];
vector<int> state;
int cnt[M];

bool check(int state)
{
for (int i = 0; i < m; i ++ )
if ((state >> i & 1) && ((state >> i + 1 & 1) || (state >> i + 2 & 1)))
return false;
return true;
}

int count(int state)
{
int res = 0;
for (int i = 0; i < m; i ++ )
if (state >> i & 1)
res ++ ;
return res;
}

int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ )
for (int j = 0; j < m; j ++ )
{
char c;
cin >> c;
g[i] += (c == 'H') << j;
}

for (int i = 0; i < 1 << m; i ++ )
if (check(i))
{
state.push_back(i);
cnt[i] = count(i);
}

for (int i = 1; i <= n; i ++ )
for (int j = 0; j < state.size(); j ++ )
for (int k = 0; k < state.size(); k ++ )
for (int u = 0; u < state.size(); u ++ )
{
int a = state[j], b = state[k], c = state[u];
if (a & b | a & c | b & c) continue;
if (g[i] & b | g[i - 1] & a) continue;
f[i & 1][j][k] = max(f[i & 1][j][k], f[i - 1 & 1][u][j] + cnt[b]);
}

int res = 0;
for (int i = 0; i < state.size(); i ++ )
for (int j = 0; j < state.size(); j ++ )
res = max(res, f[n & 1][i][j]);

cout << res << endl;

return 0;
}


#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 110 , M = 1 << 10;

int g[N]; // 表示存储每一个状态
int f[2][M][M];
int num[M];
int s[M];
int cnt;

int n , m;
int main() {

cin >> n >> m;

for (int i = 1 ; i <= n ; i ++ ) {
for (int j = 0; j < m ; j ++ ) {
char t;
cin >> t;
if (t == 'P') g[i] += 1 << (m - j - 1);
}
}

for (int i = 0 ; i < (1 << m ) ; i ++ ) {
if (!(i & i >> 1) && !(i & i >> 2)) {
s[cnt ++] = i;
for (int j = 0 ; j < m ; j ++ ) {
num[i] += (i >> j & 1);
}
}
}

for (int i = 1 ; i <= n + 2 ; i ++ ) {
for (int a = 0 ; a < cnt ; a ++ ) {
for (int b = 0 ; b < cnt ; b ++ ) {
for (int c = 0 ; c < cnt ; c ++ ) {
if (!(s[a] & s[b]) && !(s[a] & s[c]) && !(s[b] & s[c]) && (g[i] & s[a]) == s[a] && (g[i - 1] & s[b]) == s[b]) {
f[i & 1][a][b] = max(f[i & 1][a][b] , f[i - 1 & 1][b][c] + num[s[a]]);
}
}
}
}
}

cout << f[n + 2 & 1][0][0] << endl;

return 0;
}



Ayi
4天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int mod = 100000000;
const int N = 14;
int g[N]; // 各行的状态值
int cnt; // 同一行的合法状态个数
int s[1 << 14]; // 一行的合法状态集合
int f[14][1 << 14]; // 表示已经种植前i行，第i行第a个状态时的方案数

int n , m;

long long ans;
inline void init() {
cin >> n >> m;

for (int i = 1; i <= n ; i ++ ) {
for (int j = 1 ; j <= m ; j ++ ) {
int x;
cin >> x;
g[i] = (g[i] << 1) + x; // 各行的合法状态
}
}

for (int i = 0 ; i < (1 << m ) ; i ++ ) { //枚举一行所有状态
if (!(i & i >> 1))
s[cnt ++] = i;
}

f[0][0] = 1; // 什么都不选也是一种状态
for (int i = 1 ; i <= n + 1 ; i ++ ) { // 枚举行
for (int a = 0 ; a < cnt ; a ++ ) { // 枚举合法行
for (int b = 0 ; b < cnt ; b ++ ) { // 枚举第i - 1 行合法状态
if ((s[a] & g[i]) == s[a] && !(s[a] & s[b]))
f[i][a] = (f[i][a] + f[i - 1][b]) % mod;
}
}
}
for (int i = 0 ; i < (1 << m ) ; i ++ ) ans = (ans + f[n][i]) % mod; // ==  f[n + 1][0]
cout << ans << endl;
}

int main (){
init();

return 0;
}

#pragma GCC optimize(2)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include<iostream>
#include<vector>
#include<queue>
#include<map>
#include<stack>
#include<iomanip>
#include<cstring>
#include<time.h>
using namespace std;
typedef long long ll;
#define SIS std::ios::sync_with_stdio(false)
#define space putchar(' ')
#define enter putchar('\n')
#define lson root<<1
#define rson root<<1|1
typedef pair<int,int> PII;
const int mod=1e8;
const int N=2e6+10;
const int M=1e3+10;
const int inf=0x7f7f7f7f;
const int maxx=2e5+7;
const double eps=1e-6;
int gcd(int a,int b)
{
return b==0?a:gcd(b,a%b);
}

ll lcm(ll a,ll b)
{
return a*(b/gcd(a,b));
}

template <class T>
{
char c;
bool op = 0;
while(c = getchar(), c < '0' || c > '9')
if(c == '-')
op = 1;
x = c - '0';
while(c = getchar(), c >= '0' && c <= '9')
x = x * 10 + c - '0';
if(op)
x = -x;
}
template <class T>
void write(T x)
{
if(x < 0)
x = -x, putchar('-');
if(x >= 10)
write(x / 10);
putchar('0' + x % 10);
}
ll qsm(int a,int b,int p)
{
ll res=1%p;
while(b)
{
if(b&1)
res=res*a%p;
a=1ll*a*a%p;
b>>=1;
}
return res;
}
int g[N];
int n,m;
int dp[15][100005];
bool check(int x)
{
return !(x&x>>1);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=0;j<m;j++)
{
int x;
scanf("%d",&x);
g[i]+=!x<<j;
}
}
for(int i=0;i<(1<<m);i++)
if(check(i))
state.push_back(i);
for(int i=0;i<state.size();i++)
{
for(int j=0;j<state.size();j++)
{
int a=state[i],b=state[j];
if((a&b)==0)
}
}
dp[0][0]=1;
for(int i=1;i<=n+1;i++)
{
for(int a=0;a<state.size();a++)
{
{
if(g[i]&state[a]) continue;
dp[i][state[a]]=(dp[i][state[a]]+dp[i-1][state[b]])%mod;
}
}
}
printf("%d",dp[n+1][0]);

return 0;
}



Ayi
4天前

### 小国王 acwing 1064题 （题解）

1≤n≤101≤n≤10,
0≤k≤n^2

###### 输入样例：
3 2

###### 输出样例：
16


### 2 . 前沿知识

& 两个位都为1时，结果才为1
| 两个位都为0时，结果才为0
^ 异或 两个位相同为0，相异为1
~ 取反 0变1，1变0
<< 左移 各二进位全部左移若干位，高位丢弃，低位补0
>> 右移 各二进位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移）

### 思路

3 2 3 代表有一个3 * 3 的棋盘，2代表有两个国王

1 . 我们可以把每一行单独看成一个集合，最后把每一个集合的合法序列加起来即可，当然序列中可能存在重复集合，所以我们要筛选出来。

1. 那么第一行的集合 :

000 , 001 , 010 , 011 , 100 , 101 , 110 , 111 8个 (1 << n )

2.1 其中合法的序列为 ： 000 ， 001 ， 010 ， 100， 101 5个

​ i & (i << 1) 等于 0

​ 0 1 1 & 1 1 0 = 0 1 0 显然0 1 1 这个序列不合法

​ 0 0 1 & 0 1 0 = 0 合法

1. 上面我们说了行合法的情况，下面再来说说列合法的情况

0 0 0

0 1 0

0 0 0

这时我们可以把他简化一个，当前行只考虑他前面行的情况，这样也可以计算出所有合法的情况

0    0     0      不合法情况   0    1     0     0  0  1      1  0  0

0    1     0                   0    1     0     0  1  0      0  1  0


## 代码 ：

#include<bits/stdc++.h>
using namespace std;
int n,k; //棋盘行数，国王总数
int cnt; //同一行的合法状态个数
int s[1<<12]; //同一行的合法状态集
int num[1<<12]; //每个合法状态包含的国王数
long long f[12][144][1<<12];
//f[i,j,a]表示前i行放了j个国王，第i行第a个状态时的方案数

int main()
{
cin>>n>>k;
//找出一行的合法状态和每个合法状态包含的国王数
for(int i=0; i<(1<<n); i++){ //枚举一行的所有状态
if((i&i<<1)==0){ //如果不存在连续1
s[cnt++]=i; //保存一行的合法状态i
for(int j=0; j<n; j++)
num[i]+=(i>>j&1);//统计每个合法状态包含的国王数
}
}
//从第i-1行向第i行状态转移
f[0][0][0]=1;   //不放国王也是一种方案
for(int i=1; i<=n+1; i++) //枚举行
for(int j=0; j<=k; j++) //枚举国王数
for(int a=0; a<cnt; a++) //枚举第i行的合法状态
for(int b=0; b<cnt; b++) //枚举第i-1行的合法状态
{
int c=num[s[a]]; //第i行第a个状态的国王数
//可以继续放国王，同列不攻击，斜对角不攻击
if((j>=c)&&!(s[b]&s[a])&&!(s[b]&(s[a]<<1))&&!(s[b]&(s[a]>>1)))
f[i][j][a]+=f[i-1][j-c][b]; //从第i-1行向第i行转移
}
cout<<f[n+1][k][0]<<endl; //第n+1行什么都不放，相当于只在1~n行放国王

return 0;
}

if((j>=c)&&!(s[b]&s[a])&&!(s[b]&(s[a]<<1))&&!(s[b]&(s[a]>>1)))
f[i][j][a]+=f[i-1][j-c][b]; //从第i-1行向第i行转移
关于这里的 j >= c 的情况你可以把他考虑成0 1 背包问题，装得下才装，装不下就看着呗，hh
那么当前的状态就等于此时的状态 + 上一个状态的合法数。



Ayi
5天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;
const int N = 11;
LL f[N][160][160] , ans;
int n , k , cnt;
int num[160] , s[160];

inline void init() {
for (int i = 0 ; i < (1 << n ) ; i ++ ) {
if (i & (i << 1)) continue;

int sum = 0;
for (int j = 0 ; j < n ; j ++ )
if (i & (1 << j)) ++ sum;

s[++ cnt] = i;
num[cnt] = sum;
}
return ;
}

inline void dp() {

f[0][1][0] = 1;
for (int i = 1 ; i <= n ; i ++ ) {
for (int j = 1 ; j <= cnt ; j ++ ) {
for (int l = 0 ; l <= k ; l ++ ) {
if (l >= num[j]) {
for (int t = 1 ; t <= cnt ; t ++ ) {
if (!(s[t] & s[j]) && !(s[t] & (s[j] << 1)) && !(s[t] & (s[j] >> 1)))
f[i][j][l] += f[i - 1][t][l - num[j]];
}
}
}
}
}
for (int i = 1 ; i <= cnt ; i ++ )
ans += f[n][i][k];

cout << ans << endl;

return ;
}

int main() {

cin >> n >> k;
init();
dp();

}

//https://www.luogu.com.cn/problem/solution/P1896



Ayi
5天前
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, M = 110, INF = 0x3f3f3f3f;

int n, m;
int w[N];
int f[N][M][2];

int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);

memset(f, -0x3f, sizeof f);
for (int i = 0; i <= n; i ++ ) f[i][0][0] = 0;

for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
{
f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1] + w[i]);
f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - w[i]);
}

int res = 0;
for (int i = 0; i <= m; i ++ ) res = max(res, f[n][i][0]);

printf("%d\n", res);

return 0;
}



Ayi
6天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e5+10;
int f[N];

int n , m;
int main() {

cin >> n;

while (n --) {
scanf("%d",&m);
int res = 0;
int w ;
scanf("%d",&w);
f[1] = w;
for (int i = 2;  i <= m ; i ++ ) {
scanf("%d",&w);
f[i] = max(f[i - 1] , f[i - 2] + w);
}
cout << f[m] << endl;
}

return 0;
}