zhangas

Pay more attention

0%

Posted on

P1506 拯救oibh总部

题目链接
0是土地 *是墙 洪水从四面八方过来 求未被淹没的土地数量
扫一下边缘一圈，为0可以dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
char c[505][505];
int dx[5]={0,-1,1,0,0},dy[5]={0,0,0,-1,1};
void dfs(int x,int y){
    if(c[x][y]=='*')return;
    c[x][y]='-';
    for(int i=1;i<=4;i++){
        int xx=x+dx[i],yy=y+dy[i];
        if(xx>=1&&xx<=n&&yy>=1&&yy<=m){
            dfs(xx,yy);
        }
    }
}
int n,m;
int ans;
for(int i=1;i<=n;i++)dfs(i,1),dfs(i,m);
for(int i=1;i<=m;i++)dfs(1,i),dfs(n,i);
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        ans+=c[i][j]=='0'?1:0;
    }
}

B3626 跳跃机器人

题目链接
dp[i]=min(dp[i],dp[i-1]+1);
如果未到右边界才可由dp[i+1]+1转移
为偶数可由dp[i/2]+1转移
奇数可由dp[(i-1)/2]+2转移
如果未到右边界才可由dp[(i+1)/2]+2转移

1
2
3
4
5
6
7
8
9
10
11
12
13
int dp[1000005];
for(int i=2;i<=n+1;i++)dp[i]=n;//一定要初始化到N+1 考虑边界的情况
dp[1]=0;
for(int i=2;i<=n;i++){
    dp[i]=min(dp[i],dp[i-1]+1);
    if(i!=n)dp[i]=min(dp[i],dp[i+1]+1);
    if(i%2==0)dp[i]=min(dp[i],dp[i/2]+1);
    else{
        dp[i]=min(dp[i],dp[(i-1)/2]+1);
        if(i!=n)dp[i]=min(dp[i],dp[(i+1)/2]+1);
    }
}
cout<<dp[n];

P2037 电话号码

题目链接
STL模拟问题 set去重+排序 unordered_map映射个数
N<=100000 且 电话号码长度不会超过1000
O(N)*(1000)==1e9可过

1
2
3
4
5
6
7
8
9
10
11
12
13
void solve(string s){
    for(int i=0;i<s.szie();i++){
        if(s[i]>='A'&&s[i]<='Z')s[i]=...;
    }
    //处理-
    string ss='';
    for(auto i:s){
        ss+=i;
        if(ss.size()==3)ss+='-';
    }
    set.insert(ss);
    mp[ss]++;
}

P6183 [USACO10MAR] The Rock Game S

题目链接
将状态作为N位二进制表示0就是O 1就是X
求出一种方案使得相邻两种状态恰好有一位不同且无重复状态出现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int vis[1<<15+5];
bool dfs(int e){
    if(!vis[e]){
        //输出e的状态:从左到右输出二进制表示
        //与运算 两者都为1 才为1 否则为0
        for(int i=n-1;i>=0;i++){
            int t=e&(1<<i);
            if(t)cout<<'X';
            else cout<<'O';
        }
        vis[e]=1;
        //取^任意改变一位
        //异或运算 不同为1 相同为0
        for(int i=0;i<=n-1;i++){
            if(dfs(x^(1<<i)))
                return true;
        }
        return true;
    }
    return false;
}
dfs(0);

Posted on

P2362 围栏木桩

题目链接
T次询问 求序列最长上升子序列长度和个数 N^2可过
f[i]记录以a[i]结尾的序列长度
s[i]记录以a[i]结尾的序列个数
f[j]>=f[i]时 取最大个数 s[i]=s[j]
f[j]< f[i] 且 f[j]+1==f[i]时 加上a[i]使得序列长度相等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for(int i=1;i<=n;i++){
    f[i]=s[i]=1;
    for(int j=1;j<i;j++){
        if(a[j]<=a[i]){//单调不减序列
            if(f[j]>=f[i]){
                f[i]=f[j]+1;
                s[i]=s[j];
            }
            else if(f[j]+1==f[i]){
                f[i]+=f[j];
            }
        }
    }
}

P2390 地标访问

题目链接
预处理出0到位置p的地标个数
四种情况1左 2右 3先左然后拐右 4先右然后拐右左
1 2 O(1)可以得到
3 4可以筛一遍地标 O(N) 注意t可能超过整个来回的可能 我就是错这里 就30pts了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int a[100005],b[100005];//预处理坐标P到原点之间的地标个数
int aa[50005],bb[50005];//存储地标
int l,r;
int lm,rm;//两端最远距离
int lc,rc;//两端地标个数
    int ans=0;
    //1 2两种情况
	if(t>=lm)
		ans=max(ans,lc);
	else
		ans=max(ans,a[t]);
	if(t>=rm)
		ans=max(ans,rc);
	else
		ans=max(ans,b[t]);
    //3 4两种情况
    for(int i=1;i<=lc;i++){
		if(t>aa[i]*2){//足够一个来回才有意义更新答案
			int g=t-aa[i]*2;
			int res=a[aa[i]];
			if(g>=rm)res+=rc;//如果返回后也超过另一方向
			else res+=b[g];	
			ans=max(ans,res);
		}
		
	}
	for(int i=1;i<=rc;i++){
		if(t>bb[i]*2){
			int g=t-bb[i]*2;
			int res=b[bb[i]];
			if(g>=lm)res+=lc;
			else res+=a[g];
			ans=max(ans,res);
		}
	}

P1388 算式

题目链接
2≤ n ≤ 15,0 ≤ k< n

预处理出区间和再 对K个乘法的位置爆搜81pts

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int n,m;
int a[50];
int b[50];//a数组的前缀和
int vis[50];
int ans;
//put * in position e
void dfs(int e,int d,int sum){//e是位置 d是深度 sum是局部答案
	if(d==m){
		ans=max(ans,sum*(b[n]-b[e]));
		return;
	}
	for(int i=e+1;i<=n;i++){
		if(!vis[i]){
			vis[i]=1;
			dfs(i,d+1,sum*(b[i]-b[e]));
			vis[i]=0;
		}
	}
}
dfs(0,0,1);//是k+1个数的乘积 所以sum初始化为1

P1676 [USACO05FEB] Aggressive cows G

题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
sort(a+1,a+1+n);
int r=a[n]-a[1];//最大距离
int l=r;
for(int i=1;i<n;i++){
	l=min(l,a[i+1]-a[i]);//最小距离
}
//答案就在[L,R]中
while(l<r){
    int mid=(l+r+1)>>1;
    if(check(mid)){
        l=mid;
    }
    else r=mid-1;
}

check函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool check(int e){
    //检查满足最小距离为e的情况下 是否可以放置m个奶牛
    //有个贪心思想 如果从最右边的牛舍开始放都不能满足条件 那么从右侧某个牛舍开始也一定不能满足条件
    int cnt=1,res=a[1];
    for(int i=2;i<=n;i++){
        int t=a[i]-res;
        if(t>=e){
            cnt++;
            res=a[i];
        }
    }
    if(cnt>=m)return true;
    return false;
}

Posted on

P1114 “非常男女”计划

题目链接

N^2暴力 60pts

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
   int n=read();
for(int i=1;i<=n;i++){
	t[i]=read();
	if(t[i])a[i]=1;
	else b[i]=1;
}
for(int i=1;i<=n;i++){
	a[i]+=a[i-1];
	b[i]+=b[i-1];
}
int ans=0;
for(int i=1;i<=n;i++){
	for(int j=i+1;j<=n;j++){
		int aa=a[j]-a[i-1];
		int bb=b[j]-b[i-1];
		if(aa==bb)
			ans=max(ans,j-i+1);
	}
}
cout<<ans<<endl;

借助局部答案优化内层循环 100pts 不是正解,数据大仍可hack

1
2
3
4
5
6
7
8
   for(int i=1;i<=n;i++){
    int k=max(1,ans);
    for(int j=i+k;j<=n;j++){
		int aa=a[j]-a[i-1];
		int bb=b[j]-b[i-1];
			ans=max(ans,j-i+1);
	}
}

正解： 边读入边处理 分两种情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
unordered_map<int,int>mp;
int n=read();
int ans=0;
for(int i=1;i<=n;i++){
	t[i]=read();
	if(!t[i])
           t[i]=-1;//女生标注为-1
	t[i]+=t[i-1];
	if(!t[i])//当人数相等时 即和为0
		ans=i;
	else{//有-1 和 1两种可能
		if(mp[t[i]]){//减去第一次出现-1 或者1 的下标
			ans=max(ans,i-mp[t[i]]);
		}
		else mp[t[i]]=i;
	}
}
cout<<ans;

P3074 [USACO13FEB] Milk Scheduling S

题目链接
有M个要求：奶牛A必须在奶牛B前挤奶
为了尽量完成挤奶任务，聘请了一大批雇工协助任务，同一时刻足够去给任意数量的奶牛挤奶。然而，尽管奶牛可以同时挤奶，但仍需要满足以上的挤奶先后顺序。请计算挤奶过程中的最小总时间。

找出所有非孤立且入度为0的点dfs即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int a[10005];
int ru[10005];
vector<int>d[10005];
int ans;
int t[10005];
int dfs(int u){
	if(t[u]!=0)//记忆化搜索
		return t[u];
	int res=0;
	for(int i=0;i<d[u].size();i++){
		int v=d[u][i];
		//u -> v
		res=max(res,dfs(v));
	}
	return t[u]=res+a[u];
}

1<=N<=10,000 1<=M<=50,000 借助稀疏图存储路径
显然孤立点消耗的时间就是读入的时间，应该在所有孤立点中取最长时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
   for(int i=1;i<=n;i++){
	a[i]=read();
}
   while(m--){
       //a -> b
	int a=read(),b=read();
	ru[b]++;
	d[a].push_back(b);//建图
}
   for(int i=1;i<=n;i++){
       if(d[i].size()==0)
           t[i]=a[i];
   }
   for(int i=1;i<=n;i++){
	if(ru[i]==0&&d[i].size()>0){
		dfs(i);
	}
}
   for(int i=1;i<=n;i++){
       ans=max(ans,t[i]);
   }
   cout<<ans<<endl;

Posted on Edited on

时间空间复杂度

常对幂指阶
O(1)<O(log_2n)<O(n)<O(nlog_2n)<O(n^2)<O(2^n)<O(n!)<O(n^n)$

指针基础概念

&取地址符 *间接运算符

1
2
3
int number = 1;
int *p = &number;//声明一个int类型的指针指向number 存储着number的地址
printf("%d",*p);//输出指针p对应地址的值

malloc函数动态分配的空间需要手动free掉，属于内存中的堆区，系统不会自动回收空间，所以malloc和free的操作是成对出现的。

点操作符.与箭头操作符->的区别

相同点：两个都是二元操作符，其右操作符是成员的名称
不同点：点操作符左边的操作数是一个“结果为结构”的表达式；
箭头操作符左边的操作数是一个指向结构的指针

线性表

线性表的插入删除O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
void ListInsert(SqList *L,int i,int e){
    for(int j=L->length;j>=i;j--){
        L->data[j]=L->data[j-1];
    }
    L->data[i-1]=e;
    L->length++;
}
void ListDelete(SqList *L,int i){
    for(int j=i;j<L->length;j++){
        L->data[j]=L->data[j+1];
    }
    L->length--;
}

单链表

节点的创建

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct LNode{
    int val;
    struct LNode *next;
};
//typedef <数据类型> <别名>
typedef struct LNode Lnode,*LinkList;
bool InitList(LinkList L){
    L=(LNode*)malloc(sizeof(LNode));
    if(L==NULL)//内存不足
        return false;
    L->val=0;
    L->next=NULL;
    return true;
}
bool empty(LinkList L){
    if(L->next==NULL)
        return true;
    return false;
}

节点的插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
bool ListInsert(LinkList L,int i,int e){//在第i个结点插入值e
    if(i<1)return false;
    //返回第i-1个结点
    LNode *p=GetElem(L,i-1);
    //在结点p后面插入值为e的结点
    InsertNextNode(p,e);
}
bool InsertNextNode(LNode *p,int e){//在节点p后插元素e结点
    if(p==NULL)return false;
    LNode *s=(LNode *)malloc(sizeof(LNode));
    s->val=e;
    s->next=p->next;
    p->next=s;
    return true;
}
bool InsertPriorNode(LNode *p,int e){//在p结点前e的结点
    if(p==NULL)return false;
    LNode *s=(LNode *)malloc(sizeof(e));
    if(s==NULL)return false;
    //在p结点之后插入值为e的结点 再交换p的值和e
    s-next=p->next;
    p->next=s;

    s->val=p->val;
    p->val=e;
}

单链表的查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
LNode *GetElem(LinkList L,int i){//返回第i个结点
    if(i==0)return L;
    int j=0;
    LNode *p=L->next;
    while(p!=NULL&&j<i){
        p=p->next;
        j++;
    }
    if(p==NULL)return NULL;
    return p;
}
LNode *LocateElem(LinkList L,int e){//返回数据域为e的结点
    int j=0;
    LNode *p=L->next;
    while(p!=NULL&&p->val!=e){
        p=p->next;
    }
    return p;
}

链表的头插法尾插法存储

头插法可以实现链表的逆置:

1
2
3
4
5
6
7
8
9
LinkList List_HeadInsert(LinkList L){
    L=(LNode *)malloc(sizeof(LNode));
    L->next=NULL;
    int t;
    while(scanf("%d")!=EOF){
        InsertNextNode(L,t);
    }
    
}

尾插法:

1
2
3
4
5
6
7
8
9
10
11
12
13
LinkList List_TailInsert(LinkList L){
    int t;
    L=(LNode *)malloc(sizeof(LNode));
    LNode *r=L;//表尾指针
    while(scanf("%d",&t)!=EOF){
        LNode *s=(LNode *)malloc(sizeof(LNode));
        s->val=t;
        r->next=s;
        r=s;
    }
    r->next=NULL;
    return L;
}

后缀表达式

将中缀表达式转换为后缀表达式

input:    2+3*(7-4)+8/4
output:   2 3 7 4 - * + 8 4 / +

从左到右遍历表达式中每个数字和符号，遇到数字就输出，若是符号则判断它与栈顶符号的优先级，如果是右括号或者优先级不高于（也就是<=）栈顶符号，则栈顶元素依次出栈，然后将当前符号进栈，一直到结束。

1
2
3
4
5
6
int opaIsBiggerThanopb(char a,char b){//判断符号a的优先级是否比b大
    if((a=='*'||a=='/')&&b!='*'&&b!='/'&&b!='('){
        return 1;
    }
    return 0;
}

双链表

初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct DNode{
    int val;
    struct DNode *next,*prior;

}DNode,*DLinkList;
bool InitDLinkList(DLinkList L){
    L=(DNode *)malloc(sizeof(DNode));
    if(L==NULL)return false;
    L->next=NULL;
    L->prior=NULL;
    return true;

}

双链表后插,前插操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool InsertNextDNode(DNode *p,DNode *s){//在p结点后插s结点
    if(p==NULL||s==NULL)return false;
    s->next=p->next;
    if(p->next!=NULL)
        p->next->prior=s;
    s->prior=p;
    p->next=s;
    return true;
}
bool InsertPriorDNode(DNode *p,DNode *s){//在p结点前插s结点
    if(p==NULL||s==NULL)return false;
    InsertNextDNode(p->next,s);
    return true;
}

双链表后删操作和链表清空操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool DeleteNextDNode(DNode *p){//删除p的后结点
    if(p==NULL||p->next==NULL)return false;
    DNode *s=p->next;
    if(s->next!=NULL)
        s->next->prior=p;
    p->next=s->next;
    free(s);
    return true;
}
void DestoryList(DlinkList L){//清空链表
    while(L->next!=NULL)
        DeleteNextDNode(L);
    free(L);
    L=NULL;
}

顺序表和链表的优劣

总结

顺序存储：占用空间连续，支持随机存取，查找O(1)改变容量不方便，增删操作O(N)
链式存储：离散小空间分配，增删O(1)不可随机存取，查找O(N)，数据密度低

初始化

顺序存储：预分配大片连续空间
静态分配：容量不可改变。系统自动回收空间
动态分配(malloc free)：容量可改变，但移动数据时间长。需要手动free
链式存储：只需要分配一个头指针

Posted on

206. Reverse Linked List

How to exchange the nodes without changing their values?
from the side to another: u could see[pre, cur, cur->next]
it’s easy to know when “cur” gets NULL, the “pre” is at the end of linked list.
we could store “cur->next” in temp then makes “cur” at front of “pre”
so now “pre” turned to “cur” and “cur” turned to the temp’s value(used to be “cur->next”)

1
2
3
4
5
6
7
8
9
10
11
ListNode* reverseList(ListNode* head) {
        ListNode* pre=NULL;
        ListNode* cur=head;
        while(cur!=NULL){
            auto t=cur->next;
            cur->next=pre;
            pre=cur;
            cur=t; 
        }
        return pre;
}

Posted on Edited on

Foreword

进厂真不如保安，反正都学不到东西

Chapter one : 日结工作

加入本地兼职群

去问问保安,尤其是那些兼职的,黑衣服黑鞋黑裤子,然后衣服脏一点的。
你去给他一根烟,让他拉你本地兼职群,因为他们每天任务，都会建群。

比如今天1月20号，他们先建一个群，然后群里发时间你几点去。
记住这个时间，在他们之前去！！ 他们都是人够了，然后在群里说，路上的不用来了，
你还亏地铁费路费。
part-time jobs groups

初涉工作

去了之后，站队，站齐，面对面建群。群名就是工资群。
然后跟好你的带队的，记住他长啥样，下班就找他的队伍
工资发了别退，这个群以后你的带队可能会发任务，
然后上班期间，你尽量找没人地方玩手机，下班过去了就行。

工作雷区

  1. 景区 : 这是最恶心的，因为有的游客就是傻逼 + 领导还不停来
  2. 小区保安 : 来给给业主们当孙子

推荐工作

  1. 拆迁保安 : 去了朝那一坐, 抽烟玩手机就行, 反正就是装逼
    还分为便衣保安 : 钱多但要抬人的，也可能打架，千万不要去！！
    我第一回去不知道就他妈当的便衣，200多个人火拼
  2. 定时拍照 : 比如商场周围的, 每隔一个小时发点照片, 只需多拍几张，
    水印相机改时间就行。其他时间做亭子里打王者抽烟搞基没人管你
  3. 工程施工保安 ：夜班睡一觉领钱就完事了。
    他不给你发钱你直接在群里说这带队的不发钱或者扣钱，他不会把你怎么样的。
    实在不发你把衣服穿走，他自己要垫钱的。
    2019年6月19号 我带队的没给我发120工资，老子把他三套保安服，一个盾，
    一个棍子，三双鞋当垃圾扔了，本来把我删了后来又加我来了，问我衣服呢。

成为带队

通过巴结领导，说我要当你带队的，每天还能多几十的工资，在20年都快干成队长了

Posted on Edited on

按位的数学运算，也叫半加运算(不进位加法运算)
转换为二进制后 对应相同为1 不同为0
①归零律a^a=0
②恒等率a^0=a
③交换律结合律
④自反性a^b^a=b
实现交换两个数a=3 b=4
a=a^b b=a^b a=a^b 之后a=4 b=3

选数异或 蓝桥13届A组D

给定一个长度为 n 的数列 A1,A2,⋅⋅⋅,An 和一个非负整数 x，给定 m 次查询，每次询问能否从某个区间 [l,r] 中选择两个数使得他们的异或等于 x。

输入格式
输入的第一行包含三个整数 n,m,x。
第二行包含 n 个整数 A1,A2,⋅⋅⋅,An。
接下来 m 行，每行包含两个整数 [l,r] 表示询问区间 [l,r]。

输出格式
对于每个询问，如果该区间内存在两个数的异或为 x 则输出 yes，否则输出 no。
input：
4 4 1
1 2 3 4
1 4
1 2
2 3
3 3

output：
yes
no
yes
no

解题思路

性质 若a^b=x 则a^x=b
预处理出每个序号满足条件的最大左端点
再判断满足条件 [l,r] 中r的最大序数dp[r]是否比l大

样例解释

异或运算
显然维护的dp[3]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
map<int,int>mp;//key是Ai value是序号
void solve(){
    int l=read(),r=read();
    if(dp[r]>=l)puts("yes");
    else puts("no");
}
int n=read(),m=read(),x=read();
    for(int i=1;i<=n;i++){
        int t=read();
        dp[i]=max(dp[i-1],mp[t^x]);//t^x反求出 与t满足 ans^t==x的最小ans
        mp[t]=i;
    }
    //预处理 a^b=x a^x=b 处理出dp[r]满足条件的最小左序号
    
    while(m--){
        solve();
    }

Posted on Edited on

2020七段码

分类讨论数数
①不包含G
放置个数1:6 2:6 3:6 4:6 5:6 6:1
sum1=31
②包含G
放置个数1:1 2:4 3:10 4:14 5:13 6:6 7:1
sum2=49
放3个有10种情况
放3个有10种情况
放4个有14种情况
放4个有14种情况
放5个有13种情况
去3个有13种情况

共有80种情况 答案为80

Posted on Edited on

22年12月20日晚上11点16分记完了单词准备上床睡觉
但是刚躺下几分钟感觉浑身发冷打颤
大脑像是裂开一样 量了下体温发现发烧了38.9
寄了 轮到我成为小🐏人了 尝试睡觉
睡着后2点20分左右醒了 发现我浑身还是冰凉
同时感到身体像是被揍了一顿一样 翻个身都很费劲
我把衣服全穿上睡觉 8点40分醒了 到了最恶心的时刻了
头疼+嗓子吃刀片 这下真的要寄了 心里面一直在骂娘
中间又昏睡着一次 现在是中午11.30 头还是很疼 身体发软

Posted on Edited on

数位排序 前缀和与差分

若将一维数组a的[l,r]区间加上c 且时间复杂度为O(n)
设b[]是 a[]的差分 先将a的[l,+∞]加上c 再讲a[r+1,+∞]减去c

1
2
3
4
void insert(int l,int r){
    b[l]+=c;
    b[r+1]-=c; 
}

统计出现的次数cnt[]记录

1
2
3
4
5
6
7
8
9
10
11
12
while(m--){
    int l,r;scanf("%d%d",&l,&r);
    //如果直接嵌套循环会TLE
    //for(int i=l;i<=r;i++)cnt[i]++;
    //转化为差分 在循环外面求差分
    cnt[l]++;cnt[r+1]--;
}
for(int i=1;i<=n;i++)cnt[i]+=cnt[i-1];
sort(a+1,a+n+1);sort(cnt+1,cnt+1+n);
ll sum2=0;
for(int i=1;i<=n;i++)sum2+=cnt[i]*a[i];
printf("%lld",sum2-sum1);

孤独的照片

给一个只含’A’,’B’两种字符的字符串
找出所有字串中 含有单个元素的个数
input：
5
GHGHG
output：
3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
易知'A'和'B'地位相同
情况分为两种
① AAB BAAA B前面或者后面A的个数-1 即为方案数
② ABA ABAA B前后A的个数之积 即为方案数
先预处理打上序号
const int N=5e5+5;
ll g[2][N],h[2][N];
//第0行表示从前往后连续出现的个数
//第1行表示从后往前连续出现的个数
for(int i=1;i<=n;i++){
    if(c[i]=='H') h[0][i]=h[0][i-1]+1;
    else g[0][i]=g[0][i-1]+1;
}
for(int i=n;i>=1;i--){
    if(c[i]=='H') h[1][i]=h[1][i+1]+1;
    else g[1][i]=g[1][i+1]+1;
}
//遍历计算两种方案
ll ans=0;
for(int i=1;i<=n;i++){
    if(c[i]=='H'){
        if(c[i-1]=='G'&&g[0][i-1]>1) ans+=g[0][i-1]-1;
        if(c[i+1]=='G'&&g[1][i+1]>1) ans+=g[1][i+1]-1;
        if(c[i-1]=='G'&&c[i+1]=='G') ans+=g[0][i-1]*g[1][i+1];
    }
    else{
        if(c[i-1]=='H'&&h[0][i-1]>1) ans+=h[0][i-1]-1;
        if(c[i+1]=='H'&&h[1][i+1]>1) ans+=h[1][i+1]-1;
        if(c[i-1]=='H'&&c[i+1]=='H') ans+=h[0][i-1]*h[i+1];
    }
}cout<<ans<<endl;

统计次数 记忆化递归

求从1到n这n个正整数的十进制表示中 k出现的次数。
1≤ n≤ 10^6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const int N=1e6+5;
int f[N],v[N]={1};//v[0]=1 && f[0]=0;
int count(int i,int k){
    if(v[i]) return f[i];
    f[i]=f[i/10]+(i%10)==k;
    v[i]=1;
    return f[i];
}
int main(){
    int n,k;cin>>n>>k;
    int ans=0;
    for(int i=1;i<=n;i++){
        ans+=count(i,k);
    }
    cout<<ans<<endl;
}

上课睡觉 数论

有 N 堆石子，每堆的石子数量分别为 a1,a2,…,aN。
可以对石子堆进行合并操作，将两个相邻的石子堆合并为一个石子堆，例如，如果 a=[1,2,3,4,5]，合并第 2,3 堆石子，则石子堆集合变为 a=[1,5,4,5]。
我们希望通过尽可能少的操作，使得石子堆集合中的每堆石子的数量都相同。
请你输出所需的最少操作次数。本题一定有解，因为可以将所有石子堆合并为一堆。
1≤ N ≤10^5

设操作x次成功 合并后有N-x堆
设每组有y个 y*(N-x)=Σai
性质有 sum%y==0 当y最小时 x也取到最小
可以从小到大枚举sum的因数 并检测一下是否符合题意

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
const int N=1e5+5;
int n;
int a[N];
bool check(int y){
    int t=0;
    for(int i=1;i<=n;i++){
        t+=a[i];
        if(t==y)t=0;
        else if(t>y)return false;
    }
    return true;
}
void volve(){
    int mx=0,sum=0;
    cin>>n;for(int i=1;i<=n;i++){
        cin>>a[i];sum+=a[i];mx=max(a[i],mx);
    }
    if(mx==0){
        cout<<"0"<<endl;
        return;
    }
    //枚举sum的因数并检查是否符合 找出最小的y即可
    for(int i=mx;i<=sum;i++){
        if(sum%i==0&&check(i)){
            cout<<n-sum/i<<endl;
            return;
        }
    }

}
int main(){
    int t;cin>>t;
    while(t--)solve();
    return 0;
}