头像

Ayi




在线 


活动打卡代码 AcWing 1068. 环形石子合并

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




活动打卡代码 AcWing 1052. 设计密码

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




活动打卡代码 AcWing 1058. 股票买卖 V

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



活动打卡代码 AcWing 524. 愤怒的小鸟

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]);    //答案
    }
}





活动打卡代码 AcWing 292. 炮兵阵地

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




活动打卡代码 AcWing 327. 玉米田

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>
void read(T &x)
{
    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;
vector<int> state,head[N];
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)
            head[i].push_back(j);
        }
    }
    dp[0][0]=1;
    for(int i=1;i<=n+1;i++)
    {
        for(int a=0;a<state.size();a++)
        {
            for(int b:head[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×n 的棋盘上放 k 个国王,国王可攻击相邻的 8 个格子,求使它们无法互相攻击的方案总数。

输入格式

共一行,包含两个整数 n 和 k。

输出格式

共一行,表示方案总数,若不能够放置则输出00。

数据范围

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

输入样例:
3 2
输出样例:
16

2 . 前沿知识

讲述本题之前要先简述一下位运算的知识,因为状态压缩dp 需要用到一些位运算的知识

位运算概览

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

思路

本题是让我们在一个 n * n 的棋盘上求k个国王摆放正确的种数。

设每一个格子放国王为1 , 每一个格子不放格子为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个

判断方式没有相邻的1

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

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

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

我就不继续为大家演示了 . . .


之后我们需要每一个序列所摆放的国王数量,毕竟用一个少一个,能节约就节约点,h h , 开个小玩笑

根据上述 : 我们知道了集合的数量有8种,那么每一种序列的花费国王的数量就是合法序列种1的数量 。 1 放置了国王 0 代表没有放置

说了这么久该放代码了,h h

捕获.PNG

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

0 0 0

0 1 0

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

我就不 一一枚举了 :

总结就是 !(s[i] & s[j]) && !(s[i] & (s[j] >> 1)) && !(s[i] & (1<<s[j])) 这三种情况 i 表示当前行j表示0 - i - 1一行


代码 :

#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 
                那么当前的状态就等于此时的状态 + 上一个状态的合法数。



活动打卡代码 AcWing 1064. 小国王

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



活动打卡代码 AcWing 1057. 股票买卖 IV

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





活动打卡代码 AcWing 1049. 大盗阿福

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