头像

wuwendongxi

坐标CQ


访客:1795

在线 


新鲜事 原文

明天期末考试祈福


新鲜事 原文

今天上午会考结束,标准时间2h,普遍30分钟空填完的试卷(题目都是背了知识点就会的题),20分钟重新又做了一遍, 没背知识点的题不会就是不会,然后睡了一个多小时到考试结束,一个学期没上小学科,狂背二小时, 希望能及格,不然还要补考啊


新鲜事 原文

连续做了三周各种各样的DP,濒临死亡


新鲜事 原文

KMP下标每次错,只能扔AC自动机里跑的一个______。



题目链接自点

食用前注意自己加上第一步删除的边,此题解仅供参考


思路:

  • DP题
  • 环状结构通常处理方法:拆开复制两倍
  • f[i][j][1]表示:删除i~j后的最大值,f[i][j][0]表示:删除i~j后的最小值
  • 加法可直接有已完成状态最大值转移;而乘法则有四种可能,因为有负数存在

注意:

注意初始化最小最大值


#include <iostream>
#include <algorithm>
#include <cstdio>
#define inf 0x7fffffff
#define maxn 105
using namespace std;
int v[maxn],n,f[maxn][maxn][2];
char e[maxn];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i) cin>>e[i]>>v[i];
    for(int i=1;i<=2*n;++i)
        for(int j=i+1;j<=2*n;++j) f[i][j][0]=inf;
    for(int i=1;i<=2*n;++i)
        for(int j=i+1;j<=2*n;++j) f[i][j][1]=-inf;
    for(int i=1;i<=n;++i) e[i+n]=e[i],f[i+n][i+n][0]=f[i+n][i+n][1]=f[i][i][0]=f[i][i][1]=v[i];//复制两倍
    for(int len=2;len<=n;++len)//长度
        for(int i=1;i<=2*n-len+1;++i)//左界
        {
            int j=i+len-1;//右界
            for(int k=i;k<j;++k)//松弛操作
            {
                int a=f[i][k][0],b=f[k+1][j][0],c=f[i][k][1],d=f[k+1][j][1];
                if(e[k+1]=='t')
                {
                    f[i][j][0]=min(f[i][j][0],a+b);
                    f[i][j][1]=max(f[i][j][1],c+d);
                }
                if(e[k+1]=='x')
                {
                    int s[4]={a*b,a*d,c*b,c*d};
                    sort(s,s+4);
                    f[i][j][0]=min(f[i][j][0],s[0]);
                    f[i][j][1]=max(f[i][j][1],s[3]);
                }
            }
        }
    int ans=0,left,right;
    for(int i=1;i<=n;++i) ans=max(ans,f[i][i+n-1][1]);
    //自加代码:第一步删除的边
    printf("%d\n",ans);
}

马蜂不接受反驳,欢迎点赞



新鲜事 原文

AC自动机+矩阵快速幂=毒瘤


新鲜事 原文

机房一天颓



wuwendongxi
2个月前

很久没上acwing,没打过天梯 想问有关天梯匹配段位
是同段位匹配还是???
无关比赛,只是天梯
再弱弱问一句,rank榜在哪里?




wuwendongxi
2个月前

区修单查:

Description

给你N个整数A[1], A[2], … , A[N]。你需要处理两类问题:
   “C a b c”表示给A[a], A[a+1], … , A[b]之间的每个数都加上c(-10000≤c≤10000)。
   “Q a”表示询问数列中第x个数的值;

Input

输入的第一行包含两个整数N和Q(1≤N,Q≤100000);
  第二行包含N个整数Ai(-10^9≤Ai≤10^9)
  接下来Q行,表示Q个问题,形式如题;

Output

输出要求计算出的区间总和,每行一个。

Sample Input

10 5
1 2 3 4 5 6 7 8 9 10
Q 4
Q 1
Q 2
C 1 6 3
Q 2

Sample Output

4
1
2
5

c++代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
long long n,q,a[100005],sum1[100005],sum2[100005];
long long lowbit(long long x){return x&(-x);}
void add(long long x,long long d)
{
    for(long long i=x;i<=n;i+=lowbit(i))
    {
        sum1[i]+=d;//维护前缀和c[i] 
        sum2[i]+=d*(x-1);//维护前缀和c[i] * (i-1)
    }
}
long long ask(int x)
{
    long long ans=0;
    for(long long i=x;i>0;i-=lowbit(i)) ans+=x*sum1[i]-sum2[i];//通项公式 
    return ans;
}
int main()
{
    scanf("%lld%lld",&n,&q);
    for(int i=1;i<=n;++i)
    {
        scanf("%lld",&a[i]);
        add(i,a[i]-a[i-1]);//维护差分数组 
    }
    while(q--)
    {
        char f; long long f1,f2,f3; cin>>f;
        if(f=='Q')
        {
            scanf("%lld%lld",&f1,&f2);
            printf("%lld\n",ask(f2)-ask(f1-1));
        }
        else if(f=='C')
        {
            scanf("%lld%lld%lld",&f1,&f2,&f3);
            add(f1,f3); add(f2+1,-f3);
        }
    }
    return 0;
}

区修区查:

Description

给你N个整数A[1], A[2], … , A[N]。你需要处理两类问题:
   “C a b c”表示给A[a], A[a+1], … , A[b]之间的每个数都加上c(-10000≤c≤10000)。
   “Q a b”求A[a], A[a+1], … , A[b]之间数字的总和;

Input

输入的第一行包含两个整数N和Q(1≤N,Q≤100000);
  第二行包含N个整数Ai(-10^9≤Ai≤10^9)
  接下来Q行,表示Q个问题,形式如题;

Output

输出要求计算出的区间总和,每行一个。

Sample Input

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

Sample Output

4
55
9
15


附 :注意开long long,输入输出lld


C++ 代码

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
long long n,q,a[100005],sum1[100005],sum2[100005];
long long lowbit(long long x){return x&(-x);}
void add(long long x,long long d)
{
    for(long long i=x;i<=n;i+=lowbit(i))
    {
        sum1[i]+=d;//维护前缀和c[i] 
        sum2[i]+=d*(x-1);//维护前缀和c[i] * (i-1)
    }
}
long long ask(int x)
{
    long long ans=0;
    for(long long i=x;i>0;i-=lowbit(i)) ans+=x*sum1[i]-sum2[i];//通项公式 
    return ans;
}
int main()
{
    scanf("%lld%lld",&n,&q);
    for(int i=1;i<=n;++i)
    {
        scanf("%lld",&a[i]);
        add(i,a[i]-a[i-1]);//维护差分数组 
    }
    while(q--)
    {
        char f; long long f1,f2,f3; cin>>f;
        if(f=='Q')
        {
            scanf("%lld%lld",&f1,&f2);
            printf("%lld\n",ask(f2)-ask(f1-1));
        }
        else if(f=='C')
        {
            scanf("%lld%lld%lld",&f1,&f2,&f3);
            add(f1,f3); add(f2+1,-f3);
        }
    }
    return 0;
}



wuwendongxi
8个月前
  • 一、文件问题:头文件必须写全,文件输入输出不能写错。
  • 二、读入问题
    字符读入一行: 字符串数组(char s[]):cin.getline(s,sizeof(s));
    字符串(string s):getline(cin,s);
    用 scanf 读入和 printf 输出的格式,long long 一定是%lld 哟,切记切记!
  • 三、变量问题
    变量定义不能太英文化
    变量清零,注意:多组数据一定要重新清零
  • 四、运算问题
    注意运算过程中不要超数据范围,特别是乘法中间结果超 int,高精度最多使用万进制;
    注意精度问题,判断时尽量避免除法;
  • 五、内存问题:正确分析,数组不能开太大,也不能开太小
  • 提高正确率,解题速度是其次
  • 七、考场建议:
    认真审题,每道题至少读两遍;
    根据数据范围可以猜大概的算法:
    n<=100,考虑搜索;n<=2000,考虑DP(n^2);n<=1000000,考虑数学,贪心;nlogn 的算法。注意:特殊条件!
    多测试:样例数据、极限数据、特殊数据,分析能否在规定的时空范围内出解,数据范围是否够
    有些题目如果你很拿手,也肯定能做对,那么一定要保证拿满分;难题可以根据数据范围得部分分,剩余的要骗分
    (枚举验证、搜索、贪心、打表、猜数据等)
    每道题目都要写程序,不允许某个题目不写;
    注意数据类型的选择,数组的大小和内存限制(不能超过题目给的内存限制)。
    每道题目的源程序必须直接存放在 E 盘(本校)以选手编号(CQ-****)命名的目录下.
    离考试结束的最后 10 分钟一定不要再编程了,而是要仔细检查:
    ①题目的文件名,②文件输入输出,③数组范围,④调试语句是否删除,⑤题目保存的位置
    做好各项交卷的准备工作,最后用文件输入输出来测试一次。
    考试期间有任何键盘和鼠标问题可以举手找监考老师!