[关闭]
@ivorysi 2017-11-10T10:57:53.000000Z 字数 38177 阅读 774

我都会些什么

复习

语言基础

C字符串

字符串的操作也有一些说道吧……毕竟……总忘
C类型的字符串，即char数组
从1开始存会更加方便
一定要#include!这是一个很有用的头文件！memset也在里面

  1. char s[10000];
  2. scanf("%s",s+1);

如果读含有空格的字符串呢……我们可以选择getchar一个个扫进来，还有一个（在字符串空间足够的情况下）gets可以解决这个问题

  1. char s[1005];
  2. int main() {
  3.     gets(s+1);
  4.     printf("%s\n",s+1);
  5. }

字符串长度

strlen(char *s);

  1. char *s="RANK 1";
  2. int main() {
  3.     printf("%d\n",strlen(s));
  4. }

输出

  1. 6

字符串复制

strcpy(char *destin,char *source) 将第二个字符复制到第一个字符串
strncpy(char *destin,char *source,int n) 将第二个字符串的前n个字符复制给第一个

  1. char to[1005],*from="sigongzi is green sun";
  2. int main() {
  3.     strncpy(to+1,from,8);
  4.     printf("%s\n",to+1);
  5.     strcpy(to+1,from);
  6.     printf("%s\n",to+1);
  7. }

输出：

  1. sigongzi
  2. sigongzi is green sun

字符串比较

strcmp(char *s1,char *s2)
返回值为0时两字符串相等，否则返回第一个不相同的位置ASCII码的差值

  1. char *s1="sigongzi",*s2="zigongsi",*s3="sigongzi";
  2. int main() {
  3.     printf("%d\n",strcmp(s1,s2));
  4.     printf("%d\n",strcmp(s2,s1));
  5.     printf("%d\n",strcmp(s1,s3));
  6. }

输出

  1. -7
  2. 7
  3. 0

数字转化成字符串&字符串转化成数字

有两个个很妙的操作叫sprintf和sscanf

  1. char *s1="4711";
  2. int x;
  3. int main() {
  4.     sscanf(s1,"%d",&x);
  5.     printf("%d\n",x);
  6. }
  1. char s[1005];
  2. int x=4711;
  3. int main() {
  4.     sprintf(s,"%d",x);
  5.     printf("%s\n",s);
  6. }

这两个的输出都是

  1. 4711

c++ string类型

这也是一个很方便的类型
它的链接操作可以直接用+完成
比较可以用>、<、==
两个字符串之间的赋值可以用s1=s2完成
获得长度可以用s.length()
询问某个字符可以直接用数组的方式s[i]询问

插入

s.insert(pos,s2)
是在pos前面插入s2这个串

子串

s.substr(pos,n)
返回下标pos起长度为n的子串

删除

s.erase(pos,n)
删除pos起的n个字符

替换

s.replace(pos,n,s2)
将pos起n个字符替换成s2的内容

查找

s.find(s2,pos)
查找pos起s2第一次出现的位置

s.c_str

返回一个c语言风格的指针，即char*

数组间的操作

初始化

memset……这个太熟了

　数组间的复制

memcpy(dest,source,n);

  1. int a[4]={4,7,1,1};
  2. int b[4];
  3. int main() {
  4.     memcpy(b,a,sizeof(a));
  5.     siji(i,0,3) {
  6.     printf("%d ",b[i]);
  7.     }
  8. }

输出

  1. 4711

STL

queue

front() 队首元素
pop() 弹出
push() 放进去
empty() 是否为空

stack

push() 放进去
pop() 弹出来
top() 栈顶元素
empty() 是否为空

map

查找元素是否被建立过是
count()
插入可以像数组一样插入，询问可以像数组一样询问

set & multiset

注意multiset删除的时候删除某个特定元素需要用迭代器
find()查找
erase()删除
insert()插入
一个begin()指针是真实存在的，另一个end()作为结束标记是悬空的，不能访问

vector

一般就是push_back()和pop_back()

lower_bound()和upper_bound()

  1. int a[11]={1,2,3,4,5,6,7,7,7,7,8};
  2. int main() {
  3.     int pos1=lower_bound(a,a+11,7)-a;
  4.     int pos2=upper_bound(a,a+11,7)-a;
  5.     printf("%d %d\n",pos1,pos2);
  6. }

输出

  1. 6 10

也就是说lower_bound是大于等于某个数的第一个
upper_bound是大于某个数的第一个

算法

高精度

这大概应该是从入门就接触的第一个算法，也是将旷日持久陪伴我们的算法……这个算法的原理在小学就学过了……可惜细节太多了，唯一的办法就是多写了，鉴于noip考的算法不可能考裸的高精，一般的dp只涉及乘法和加法……那么板子先放在这里了

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <vector>
  5. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  6. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  7. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  8. //#define ivorysi
  9. using namespace std;
  10. typedef long long ll;
  11. const int BASE=100000000;
  12. const int WIDTH=8;
  13. struct bignum {
  14.     vector<int> v;
  15.     bignum operator = (long long num) {
  16.     v.clear();
  17.     do{
  18.         v.push_back(num%BASE);
  19.         num/=BASE;
  20.     }while(num>0);
  21.     return *this;
  22.     }
  23.     bignum operator = (const string &str) {
  24.     v.clear();
  25.     int len=(str.length()-1)/WIDTH+1,x;
  26.     xiaosiji(i,0,len) {
  27.         int end=str.length()-i*WIDTH;
  28.         int st=max(0,end-WIDTH);
  29.         sscanf(str.substr(st,end-st).c_str(),"%d",&x);
  30.         v.push_back(x);
  31.         }
  32.     return *this;
  33.     }
  34.     bignum operator + (const bignum &b) {
  35.     int lena=v.size(),lenb=b.v.size();
  36.     bignum c;
  37.     c.v.clear();
  38.     int p=0,g=0,x;
  39.     while(1) {
  40.         x=g;
  41.         if(p<lena) x+=v[p];
  42.         if(p<lenb) x+=b.v[p];
  43.         if(p>=lena && p>=lenb && x==0) {break;}
  44.         c.v.push_back(x%BASE);
  45.         g=x/BASE;
  46.         ++p;
  47.     }
  48.     return c;
  49.     }
  50.     bignum operator *(const bignum &b) {
  51.     int lena=v.size(),lenb=b.v.size();
  52.     bignum c;
  53.     c.v.clear();
  54.     siji(i,0,lena+lenb) c.v.push_back(0);
  55.     xiaosiji(i,0,lena) {
  56.         ll g=0;
  57.         xiaosiji(j,0,lenb) {
  58.         ll x=(ll)v[i]*b.v[j]+g+c.v[i+j];
  59.         c.v[i+j]=x%BASE;
  60.         g=x/BASE;
  61.         }
  62.         int t=i+lenb;
  63.         while(g) {
  64.         ll x=g+c.v[t];
  65.         c.v[t]=x%BASE;
  66.         g=x/BASE;
  67.         ++t;
  68.         }
  69.     }
  70.     int s=c.v.size();
  71.     gongzi(i,s-1,1) {
  72.         if(c.v[i]==0) {c.v.pop_back();}
  73.         else break;
  74.     }
  75.     return c;
  76.     }
  77.     void out() {
  78.     int s=v.size()-1;
  79.     printf("%d",v[s]);
  80.     --s;
  81.     gongzi(i,s,0) {
  82.         printf("%08d",v[i]);
  83.     }
  84.     putchar('\n');
  85.     }
  86. }a,b;
  87. string stra,strb;
  88. int main() {
  89.     cin>>stra>>strb;
  90.     a=stra;b=strb;
  91.     bignum t=a*b;
  92.     t.out();
  93. }

归并排序求逆序对

这个名字看的我很眼熟，但我的确是很久没写了
noip2013火柴排队

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <cstring>
  6. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  7. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  8. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  9. #define pii pair<int,int>
  10. #define fi first
  11. #define se second
  12. #define mod  99999997
  13. //#define ivorysi
  14. using namespace std;
  15. typedef long long ll;
  16. int read() {
  17.     int res=0;
  18.     char c=getchar();
  19.     while(c<'0' || c>'9') c=getchar();
  20.     while(c>='0' && c<='9') {
  21.     res=res*10-'0'+c;
  22.     c=getchar();
  23.     }
  24.     return res;
  26. }
  27. pii a[1000005],b[1000005];
  28. int n;
  29. int c[1000005],num[1000005];
  30. ll ans;
  31. void merge(int l,int m,int r) {
  32.     int pa=l,pb=m+1,p=l;
  33.     while(pa<=m && pb<=r) {
  34.     if(c[pa]<c[pb]) {
  35.         num[p++]=c[pa++];
  36.     }
  37.     else {
  38.         num[p++]=c[pb++];
  39.         ans+=(m-pa+1);
  40.         ans%=mod;
  41.     }
  42.     }
  43.     while(pa<=m) {num[p++]=c[pa++];}
  44.     while(pb<=r) {num[p++]=c[pb++];}
  45.     siji(i,l,r) c[i]=num[i];
  46. }
  47. void mergesort(int l,int r) {
  48.     if(l<r) {
  49.     int m=(l+r)>>1;
  50.     mergesort(l,m);
  51.     mergesort(m+1,r);
  52.     merge(l,m,r);
  53.     }
  54. }
  55. int main() {
  56. #ifdef ivorysi
  57.     freopen("f1.in","r",stdin);
  58. #endif
  59.     n=read();
  60.     siji(i,1,n) {
  61.     a[i].fi=read();
  62.     a[i].se=i;
  63.     }
  64.     siji(i,1,n) {
  65.     b[i].fi=read();
  66.     b[i].se=i;
  67.     }
  68.     sort(a+1,a+n+1);
  69.     sort(b+1,b+n+1);
  70.     siji(i,1,n) {
  71.     c[a[i].se]=b[i].se;
  72.     }
  73.     mergesort(1,n);
  74.     printf("%lld\n",ans);
  75. }

树状数组求逆序对

虽然应该归类到数据结构，但是都是求逆序对，就放一起了
noip2013火柴排队

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <cstring>
  6. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  7. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  8. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  9. #define pii pair<int,int>
  10. #define fi first
  11. #define se second
  12. #define mod  99999997
  13. //#define ivorysi
  14. using namespace std;
  15. typedef long long ll;
  16. int read() {
  17.     int res=0;
  18.     char c=getchar();
  19.     while(c<'0' || c>'9') c=getchar();
  20.     while(c>='0' && c<='9') {
  21.     res=res*10-'0'+c;
  22.     c=getchar();
  23.     }
  24.     return res;
  26. }
  27. pii a[1000005],b[1000005];
  28. int n;
  29. int c[1000005];
  30. ll ans;
  31. int tr[1000005];
  32. int lowbit(int x){return x&(-x);}
  33. void change(int pos) {
  34.     while(pos<=n) {
  35.     ++tr[pos];
  36.     pos+=lowbit(pos);
  37.     }
  38. }
  39. int query(int pos) {
  40.     int res=0;
  41.     while(pos>0) {
  42.     res+=tr[pos];
  43.     pos-=lowbit(pos);
  44.     }
  45.     return res;
  46. }
  47. int main() {
  48. #ifdef ivorysi
  49.     freopen("f1.in","r",stdin);
  50. #endif
  51.     n=read();
  52.     siji(i,1,n) {
  53.     a[i].fi=read();
  54.     a[i].se=i;
  55.     }
  56.     siji(i,1,n) {
  57.     b[i].fi=read();
  58.     b[i].se=i;
  59.     }
  60.     sort(a+1,a+n+1);
  61.     sort(b+1,b+n+1);
  62.     siji(i,1,n) {
  63.     c[a[i].se]=b[i].se;
  64.     }
  65.     siji(i,1,n) {
  66.     ans+=query(n)-query(c[i]-1);
  67.     change(c[i]);
  68.     ans%=mod;
  69.     }
  70.     printf("%lld\n",ans);
  71. }

　求LIS

导弹拦截
我似乎已经很久没写过这个东西了
lower_bound 和upper_bound 真好用

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  6. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  7. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  8. //#define ivorysi
  9. using namespace std;
  10. typedef long long ll;
  11. int n;
  12. int a[100005];
  13. int f[100005],cnt;
  14. void solve() {
  15.     while(~scanf("%d",&a[++n]));
  16.     --n;
  17.     gongzi(i,n,1) {
  18.     if(a[i]>=f[cnt]) {
  19.         f[++cnt]=a[i];
  20.     }
  21.     else {
  22.         int x=upper_bound(f,f+cnt,a[i])-f;
  23.         if(a[i]<f[x]) f[x]=a[i];
  24.     }
  25.     }
  26.     printf("%d\n",cnt);
  28.     cnt=0;
  29.     siji(i,1,n) {
  30.     if(a[i]>f[cnt]) {
  31.         f[++cnt]=a[i];
  32.     }
  33.     else {
  34.         int x=lower_bound(f,f+cnt,a[i])-f;
  35.         if(a[i]<f[x]) f[x]=a[i];
  36.     }
  37.     }
  38.     printf("%d\n",cnt);
  39. }
  40. int main() {
  41. #ifdef ivorysi
  42.     freopen("f1.in","r",stdin);
  43. #endif
  44.     solve();
  45. }

扩展gcd

ax+by=g的几个解

1352 集合计数

基准时间限制：1 秒 空间限制：131072 KB 分值: 20 难度：3级算法题
给出N个固定集合{1，N},{2,N-1},{3,N-2},...,{N-1,2},{N,1}.求出有多少个集合满足：第一个元素是A的倍数且第二个元素是B的倍数。
提示：
对于第二组测试数据，集合分别是：{1,10},{2,9},{3,8},{4,7},{5,6},{6,5},{7,4},{8,3},{9,2},{10,1}.满足条件的是第2个和第8个。

Input

第1行：1个整数T（1<=T<=50000)，表示有多少组测试数据。
第2 - T+1行：每行三个整数N，A,B（1<=N，A，B<=2147483647)

Output

对于每组测试数据输出一个数表示满足条件的集合的数量，占一行。

Input示例

2
5 2 4
10 2 3

Output示例

1
2

ax+by=n+1 看看n+1是不是g的倍数
如果是的话就从x的第一个解开始计算，每一个解的距离都是lcm（a,b）
如果第一个x是0的话就让x=b/g

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  6. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  7. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  8. #define MAXN 100005
  9. //#define ivorysi
  10. using namespace std;
  11. typedef long long ll;
  13. ll read() {
  14.     ll res=0;
  15.     char c=getchar();
  16.     while(c < '0' || c > '9') c=getchar();
  17.     while(c>='0' && c<='9') {
  18.     res=res*10-'0'+c;
  19.     c=getchar();
  20.     }
  21.     return res;
  22. }
  24. int gcd(ll a,ll b) {
  25.     return b==0 ? a:gcd(b,a%b);
  26. }
  27. int ex_gcd(ll a,ll b,ll &x,ll &y) {
  28.     if(b==0) {
  29.     x=1;y=0;
  30.     return a;
  31.     }
  32.     else {
  33.     int res=ex_gcd(b,a%b,y,x);
  34.     y-=a/b*x;
  35.     return res;
  36.     }
  37. }
  38. int t;
  39. ll n,a,b;
  40. void solve() {
  41.     n=read();a=read();b=read();
  42.     ll x=0,y=0;
  43.     ll g=ex_gcd(a,b,x,y);
  44.     x=((x%b)+b)%b;
  45.     if((n+1)%g!=0) {
  46.     puts("0");
  47.     return;
  48.     }
  49.     else {
  50.     x=(ll)x*((n+1)/g)%(b/g);
  51.     if(x==0) x=b/g;
  52.     if((ll)x*a>n) {
  53.         puts("0");return;
  54.     }
  55.     int ans=(n-a*x)/((ll)a/g*b)+1;
  56.     printf("%d\n",ans);
  57.     }
  58. }
  59. int main() {
  60. #ifdef ivorysi
  61.     freopen("f1.in","r",stdin);
  62. #endif
  63.     t=read();
  64.     while(t--) {
  65.     solve();
  66.     }
  68. }

背包

暴力（violent）

时间：1s(如果用lemon评测，请开2s)
空间：64MB
如果认为本题正解有误或数据有误或正解不够优请通知我。
17.11.1：数据重新更新，如果仍有问题请通知我。
背景

XYC是未来OI的红太阳，今天就要参加2117 NOI professional，并打算ak全场。
但是很不幸，今年出2117 NOI professional的人是ZSW，他出了很多道大模拟题目，并伴随各种高深算法，很多学生纷纷爆零，走上了高考的不归路。
但是XYC可是未来的红太阳啊！就算题目很难，XYC神犇也不会爆零并且轻松RANK1啊，但是就算能够轻松省一，XYC还想要挑战自己的极限，得到尽可能高的分。
题面描述

本场2117 NOI professional的考试时间为TTT，共有NNN道题，当时间T<0T<0T<0时XYC就需要停止答题。
XYC初始的耐心值为WWW，当W<0W<0W<0，他就会厌倦去做这套题。
请注意做任何导致W<0W<0W<0和T<0T<0T<0的操作都是犯规的。
如果XYC下定决心要做某一道题，他就需要花费ttt的时间和www的耐心去读完题目。
当XYC读完题目后，XYC可以有三种选择且只能选择其中一种：
1. 写正解，XYC将花费tmaxtmaxtmax的时间和wmaxwmaxwmax的耐心并获得kmaxkmaxkmax的分数。
2. 写暴力，XYC有mmm种暴力可以写，每一个暴力需要花费tititi的时间和wiwiwi的耐心并获得kikiki的分数。每一道题每一种暴力只可以写一次，但XYC可以写多种暴力。
3. 写固输，XYC可以花费0的时间和0的耐心并获得1分。
请注意XYC一次只能做一件事（包括看题面，写正解，写一种暴力，写固输）。
XYC的目标是他得到的分数sumsumsum最大。
输入描述

第一行三个正整数NNN、TTT、WWW。
对于每一道题，其第一行为正整数ttt、www。
其第二行为三个正整数tmaxtmaxtmax、wmaxwmaxwmax、kmaxkmaxkmax。
其第三行为mmm。
其第四行到m+3m+3m+3行，每行三个正整数tititi、wiwiwi、kikiki。
输出描述

一行一个整数sumsumsum。
样例输入1

2 20 30
5 10
20 20 50
2
10 5 20
6 8 10
5 3
4 8 10
3
2 1 1
4 5 8
2 3 1

样例输出1

21

样例输入2

1 50 50
1 1
50 50 10000
0

样例输出2

1

数据规模

100%的数据满足，
N<=100N<=100N<=100，T<=50T<=50T<=50，W<=50W<=50W<=50，m<=40m<=40m<=40.
ki<=105ki<=10^5ki<=105，kmax<=107kmax<=10^7kmax<=107.
ttt，www，tmaxtmaxtmax，wmax<=100wmax<=100wmax<=100.

这道题很好
这道题的算法全名叫多维分组01背包……就是状态多了点，转移思路还是很简单的
适合练板子

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  6. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  7. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  8. #define MAXN 100005
  9. //#define ivorysi
  10. using namespace std;
  11. typedef long long ll;
  12. int n,m,T,W;
  13. ll vio[55][55],f[105][55][55],ans;
  14. ll t,w,tmax,kmax,wmax;
  15. ll tim[55],pat[55],val[55];
  16. int read() {
  17.     int res=0;
  18.     char c=getchar();
  19.     while(c < '0' || c > '9') c=getchar();
  20.     while(c>='0' && c<='9') {
  21.     res=res*10+c-'0';
  22.     c=getchar();
  23.     }
  24.     return res;
  25. }
  26. void solve() {
  27.     n=read();T=read();W=read();
  28.     siji(i,1,n) {
  30.     siji(j,0,T) {
  31.         siji(l,0,W) {
  32.         f[i][j][l]=max(f[i-1][j][l],f[i][j][l]);
  33.         }
  34.     }
  35.     t=read();
  36.     w=read();
  37.     tmax=read();wmax=read();kmax=read();
  38.     gongzi(j,T,t) {
  39.         gongzi(l,W,w) {
  40.         if(j>=tmax+t && l>=wmax+w)f[i][j][l]=max(f[i-1][j-tmax-t][l-wmax-w]+kmax,f[i][j][l]);
  41.         f[i][j][l]=max(f[i-1][j-t][l-w]+1,f[i][j][l]);
  42.         }
  43.     }
  44.     memset(vio,0,sizeof(vio));
  45.     m=read();
  46.     siji(k,1,m) {
  47.         tim[k]=read();pat[k]=read();val[k]=read();
  48.         gongzi(j,T,tim[k]) {
  49.         gongzi(l,W,pat[k]) {
  50.             vio[j][l]=max(vio[j][l],vio[j-tim[k]][l-pat[k]]+val[k]);
  51.         }
  52.         }
  53.     }
  54.     siji(ti,0,T) {
  55.         siji(wi,0,W) {
  56.         gongzi(j,T,ti+t) {
  57.             gongzi(l,W,wi+w){
  58.             f[i][j][l]=max(f[i-1][j-ti-t][l-wi-w]+vio[ti][wi],f[i][j][l]);
  59.             }
  60.         }
  61.         }
  62.     }
  63.     }
  64.     siji(j,0,T) {
  65.     siji(l,0,W) {
  66.         ans=max(ans,f[n][j][l]);
  67.     }
  68.     }
  69.     printf("%lld\n",ans);
  70. }
  71. int main() {
  72. #ifdef ivorysi
  73.     freopen("f1.in","r",stdin);
  74. #endif
  75.     solve();
  76. }

倍增求lca

板子……
注意一下根节点的deep是1

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  6. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  7. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  8. #define MAXN 500005
  9. //#define ivorysi
  10. using namespace std;
  11. typedef long long ll;
  12. int read() {
  13.     int res=0;
  14.     char c=getchar();
  15.     while(c<'0' || c>'9') c=getchar();
  16.     while(c>='0' && c<='9') {
  17.     res=res*10+c-'0';
  18.     c=getchar();
  19.     }
  20.     return res;
  21. }
  22. struct node {
  23.     int to,next;
  24. }edge[MAXN*2];
  25. int head[MAXN],sumedge;
  26. void add(int u,int v){
  27.     edge[++sumedge].to=v;
  28.     edge[sumedge].next=head[u];
  29.     head[u]=sumedge;
  30. }
  31. void addtwo(int u,int v) {
  32.     add(u,v);add(v,u);
  33. }
  34. int fa[MAXN][25],dep[MAXN];
  35. int n,m,s;
  36. void dfs(int u) {
  37.     for(int i=head[u];i;i=edge[i].next) {
  38.     int v=edge[i].to;
  39.     if(v!=fa[u][0]) {
  40.         fa[v][0]=u;
  41.         dep[v]=dep[u]+1;
  42.         dfs(v);
  43.     }
  44.     }
  45. }
  46. int lca(int a,int b) {
  47.     if(dep[a]<dep[b]) swap(a,b);
  48.     int l=20;
  49.     while(dep[a]>dep[b]) {
  50.     if(dep[fa[a][l]]>=dep[b]) {
  51.         a=fa[a][l];
  52.     }
  53.     --l;
  54.     }
  55.     if(a==b) return a;
  56.     l=20;
  57.     while(fa[a][0]!=fa[b][0]) {
  58.     if(fa[a][l]!=fa[b][l]) {
  59.         a=fa[a][l];
  60.         b=fa[b][l];
  61.     }
  62.     --l;
  63.     }
  64.     return fa[a][0];
  65. }
  66. void solve() {
  67.     n=read();m=read();s=read();
  68.     int x,y;
  69.     xiaosiji(i,1,n) {
  70.     x=read();
  71.     y=read();
  72.     addtwo(x,y);
  73.     }
  74.     dep[s]=1;
  75.     dfs(s);
  76.     siji(j,1,20) {
  77.     siji(i,1,n) {
  78.         fa[i][j]=fa[fa[i][j-1]][j-1];
  79.     }
  80.     }
  81.     int a,b;
  82.     siji(i,1,m) {
  83.     a=read();b=read();
  84.     int c=lca(a,b);
  85.     printf("%d\n",c);
  86.     }
  87. }
  88. int main() {
  89. #ifdef ivorysi
  90.     freopen("f1.in","r",stdin);
  91. #endif
  92.     solve();
  93. }

tarjan求lca

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  6. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  7. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  8. #define MAXN 500005
  9. //#define ivorysi
  10. using namespace std;
  11. typedef long long ll;
  12. int read() {
  13.     int res=0;
  14.     char c=getchar();
  15.     while(c<'0' || c>'9') c=getchar();
  16.     while(c>='0' && c<='9') {
  17.     res=res*10+c-'0';
  18.     c=getchar();
  19.     }
  20.     return res;
  21. }
  22. struct node {
  23.     int to,next;
  24. }edge[MAXN*2];
  25. struct data {
  26.     int to,next,lca;
  27. }qedge[MAXN*2];
  28. int head[MAXN],sumedge,qhead[MAXN],qsum=1,vis[MAXN],fa[MAXN];
  29. int n,m,s;
  30. void add(int u,int v){
  31.     edge[++sumedge].to=v;
  32.     edge[sumedge].next=head[u];
  33.     head[u]=sumedge;
  34. }
  35. void qadd(int u,int v) {
  36.     qedge[++qsum].to=v;
  37.     qedge[qsum].next=qhead[u];
  38.     qhead[u]=qsum;
  39. }
  40. void qaddtwo(int u,int v) {
  41.     qadd(u,v);qadd(v,u);
  42. }
  43. void addtwo(int u,int v) {
  44.     add(u,v);add(v,u);
  45. }
  46. int getfa(int x) {
  47.     return fa[x]==x ? x:fa[x]=getfa(fa[x]);
  48. }
  49. void dfs(int u,int f) {
  50.     for(int i=qhead[u];i;i=qedge[i].next) {
  51.     int v=qedge[i].to;
  52.     if(vis[v]) {
  53.         qedge[i].lca=getfa(v);
  54.         qedge[i^1].lca=getfa(v);
  55.     }
  56.     }
  57.     vis[u]=1;
  58.     for(int i=head[u];i;i=edge[i].next) {
  59.     int v=edge[i].to;
  60.     if(v!=f) {
  61.         dfs(v,u);
  62.         fa[getfa(v)]=getfa(u);
  63.     }
  64.     }
  65. }
  66. void solve() {
  67.     n=read();m=read();s=read();
  68.     int x,y;
  69.     xiaosiji(i,1,n) {
  70.     x=read();
  71.     y=read();
  72.     addtwo(x,y);
  73.     }
  74.     siji(i,1,m) {
  75.     x=read();
  76.     y=read();
  77.     qaddtwo(x,y);
  78.     }
  79.     siji(i,1,n) {
  80.     fa[i]=i;
  81.     }
  82.     dfs(s,0);
  83.     siji(i,1,n) {
  84.     printf("%d\n",qedge[i*2].lca);
  85.     }
  86. }
  87. int main() {
  88. #ifdef ivorysi
  89.     freopen("f1.in","r",stdin);
  90. #endif
  91.     solve();
  92. }

tarjan缩点

这道题还有求一条点值和最大的路径
要注意每个点的编号和每个点颜色编号的转换
颜色编号的降序其实就是缩点之后的拓扑序

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  8. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  9. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  10. #define MAXN 10004
  11. #define MAXM 100005
  12. //#define ivorysi
  13. using namespace std;
  14. typedef long long ll;
  15. int read() {
  16.     int res=0;
  17.     char c=getchar();
  18.     while(c<'0' || c>'9') c=getchar();
  19.     while(c>='0' && c<='9') {
  20.     res=res*10+c-'0';
  21.     c=getchar();
  22.     }
  23.     return res;
  24. }
  25. struct node {
  26.     int to,next;
  27. }edge[MAXM*2];
  28. int head[MAXN],sumedge;
  29. int n,m;
  30. void add(int u,int v){
  31.     edge[++sumedge].to=v;
  32.     edge[sumedge].next=head[u];
  33.     head[u]=sumedge;
  34. }
  35. void addtwo(int u,int v) {
  36.     add(u,v);add(v,u);
  37. }
  38. int col[MAXN],tot,instack[MAXN],dfn[MAXN],low[MAXN],cnt;
  39. int val[MAXN],sum[MAXN],dp[MAXN];
  40. vector<int> pos[MAXN];
  41. stack<int> s;
  42. void tarjan(int u) {
  43.     instack[u]=1;
  44.     dfn[u]=low[u]=++cnt;
  45.     s.push(u);
  46.     for(int i=head[u];i;i=edge[i].next) {
  47.     int v=edge[i].to;
  48.     if(!dfn[v]) {
  49.         tarjan(v);
  50.         low[u]=min(low[v],low[u]);
  51.     }
  52.     else if(instack[v]==1) {
  53.         low[u]=min(dfn[v],low[u]);
  54.     }
  55.     }
  56.     if(low[u]>=dfn[u]) {
  57.     ++tot;
  58.     while(1) {
  59.         int x=s.top();s.pop();
  60.         pos[tot].push_back(x);
  61.         instack[x]=2;
  62.         col[x]=tot;
  63.         if(x==u) break;
  64.     }
  65.     }
  66. }
  67. void solve() {
  68.     n=read();m=read();
  69.     int x,y;
  70.     siji(i,1,n) {
  71.     val[i]=read();
  72.     }
  73.     siji(i,1,m) {
  74.     x=read();y=read();
  75.     add(x,y);
  76.     }
  77.     siji(i,1,n) {
  78.     if(!dfn[i]) {
  79.         tarjan(i);
  80.     }
  81.     }
  82.     siji(i,1,n) {
  83.     sum[col[i]]+=val[i];
  84.     }
  85.     siji(i,1,tot) dp[i]+=sum[i];
  86.     gongzi(i,tot,1) {
  87.     int s=pos[i].size();
  88.     xiaosiji(j,0,s) {
  89.         int u=pos[i][j];
  90.         for(int k=head[u];k;k=edge[k].next) {
  91.         int t=edge[k].to;
  92.         if(col[t]!=col[u]) {
  93.             dp[col[t]]=max(sum[col[t]]+dp[col[u]],dp[col[t]]);
  94.         }
  95.         }
  96.     }
  97.     }
  98.     int ans=0;
  99.     siji(i,1,tot) {
  100.     ans=max(ans,dp[i]);
  101.     }
  102.     printf("%d\n",ans);
  103. }
  104. int main() {
  105. #ifdef ivorysi
  106.     freopen("f1.in","r",stdin);
  107. #endif
  108.     solve();
  109. }

tarjan求割点

我……我发现我又忘了这玩意了
这个东西注意我们在走到搜索树的儿子边时要用儿子的low更新自身（和tarjan求强连通分量差不多），然后呢，这个点必须不是搜索树的根，然后再来判断这个点的某个儿子能不能走到这个点上面，如果不能说明这个点就是割点
注意判断这个东西不是搜索树的根！！！

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  8. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  9. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  10. #define MAXN 10004
  11. #define MAXM 100005
  12. //#define ivorysi
  13. using namespace std;
  14. typedef long long ll;
  15. int read() {
  16.     int res=0;
  17.     char c=getchar();
  18.     while(c<'0' || c>'9') c=getchar();
  19.     while(c>='0' && c<='9') {
  20.     res=res*10+c-'0';
  21.     c=getchar();
  22.     }
  23.     return res;
  24. }
  25. struct node {
  26.     int to,next;
  27. }edge[MAXM*2];
  28. int head[MAXN],sumedge;
  29. int n,m;
  30. void add(int u,int v){
  31.     edge[++sumedge].to=v;
  32.     edge[sumedge].next=head[u];
  33.     head[u]=sumedge;
  34. }
  35. void addtwo(int u,int v) {
  36.     add(u,v);add(v,u);
  37. }
  38. int dfn[MAXN],low[MAXN],cnt,ans;
  39. bool ispos[MAXN];
  40. void tarjan(int u,int fa) {
  41.     dfn[u]=low[u]=++cnt;
  42.     int son=0;
  43.     for(int i=head[u];i;i=edge[i].next) {
  44.     int v=edge[i].to;
  45.     if(!dfn[v]) {
  46.         tarjan(v,u);
  47.         ++son;
  48.         low[u]=min(low[v],low[u]);
  49.         if(fa!=0 && low[v]>=dfn[u]) {
  50.         ispos[u]=1;
  51.         }
  52.     }
  53.     else if(v!=fa){
  54.         low[u]=min(dfn[v],low[u]);
  55.     }
  56.     }
  57.     if(fa==0 && son>=2) {
  58.     ispos[u]=1;
  59.     }
  60. }
  61. void solve() {
  62.     n=read();m=read();
  63.     int x,y;
  64.     siji(i,1,m) {
  65.     x=read();y=read();
  66.     addtwo(x,y);
  67.     }
  68.     siji(i,1,n) {
  69.     if(!dfn[i]) {
  70.         tarjan(i,0);
  71.     }
  72.     }
  73.     siji(i,1,n) {
  74.     if(ispos[i]) {
  75.         ++ans;
  76.     }
  77.     }
  78.     printf("%d\n",ans);
  79.     siji(i,1,n) {
  80.     if(ispos[i]) {
  81.         printf("%d ",i);
  82.     }
  83.     }
  84.     puts("");
  85. }
  86. int main() {
  87. #ifdef ivorysi
  88.     freopen("f1.in","r",stdin);
  89. #endif
  90.     solve();
  91. }

线性求逆元

其实我是最近才会的，单个数逆元的求法就是普通的费马小定理快速幂
然后线性的有个递推式

  1. siji(i,2,n) {
  2.     inv[i]=(p-p/i)*inv[p%i]%p;
  3. }

证明设 



  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  8. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  9. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  10. #define MAXN 3000005
  11. //#define ivorysi
  12. using namespace std;
  13. typedef long long ll;
  14. ll read() {
  15.     ll res=0,neg=1;
  16.     char c=getchar();
  17.     while(c<'0' || c>'9') {
  18.     if(c=='-') neg=-1;
  19.     c=getchar();
  20.     }
  21.     while(c>='0' && c<='9') {
  22.     res=res*10+c-'0';
  23.     c=getchar();
  24.     }
  25.     return res*neg;
  26. }
  27. int n,p;
  28. ll inv[MAXN];
  29. void solve() {
  30.     n=read();p=read();
  31.     inv[1]=1;
  32.     printf("%lld\n",inv[1]);
  33.     siji(i,2,n) {
  34.     inv[i]=(p-p/i)*inv[p%i]%p;
  35.     printf("%lld\n",inv[i]);
  36.     }
  38. }
  39. int main() {
  40. #ifdef ivorysi
  41.     freopen("f1.in","r",stdin);
  42. #endif
  43.     solve();
  44. }

Lucas定理


证明如下



中的系数
我们发现可以消掉一些系数然后式子就变成了……


能达到的情况只有i=t且j=q
所以 

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  8. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  9. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  10. #define MAXN 3000005
  11. //#define ivorysi
  12. using namespace std;
  13. typedef long long ll;
  14. ll read() {
  15.     ll res=0,neg=1;
  16.     char c=getchar();
  17.     while(c<'0' || c>'9') {
  18.     if(c=='-') neg=-1;
  19.     c=getchar();
  20.     }
  21.     while(c>='0' && c<='9') {
  22.     res=res*10+c-'0';
  23.     c=getchar();
  24.     }
  25.     return res*neg;
  26. }
  27. int n,m,p,T;
  28. ll inv[MAXN],fac[MAXN];
  29. ll cnm(int y,int z) {
  30.     return fac[y]*inv[z]%p*inv[y-z]%p;
  31. }
  32. ll fpow(ll x,int c) {
  33.     ll res=1,t=x;
  34.     while(c) {
  35.     if(c&1) res=res*t%p;
  36.     t=t*t%p;
  37.     c>>=1;
  38.     }
  39.     return res;
  40. }
  41. ll Lucas(int y,int k) {
  42.     int q,r;
  43.     ll res=1;
  44.     while(y>0 && k>0) {
  45.     if(y<k) return 0;
  46.     r=y%p;q=k%p;
  47.     if(r<q) return 0;
  48.     res=res*cnm(r,q)%p;
  49.     y=y/p;k=k/p;
  50.     }
  51.     return res;
  52. }
  53. void solve() {
  54.     n=read();
  55.     m=read();
  56.     p=read();
  57.     fac[0]=1;
  58.     siji(i,1,p-1) {
  59.     fac[i]=fac[i-1]*i%p;
  60.     }
  61.     inv[p-1]=fpow(fac[p-1],p-2);
  62.     gongzi(i,p-1,1) {
  63.     inv[i-1]=inv[i]*i%p;
  64.     }
  65.     ll ans=Lucas(n+m,m);
  66.     printf("%lld\n",ans);
  67. }
  68. int main() {
  69. #ifdef ivorysi
  70.     freopen("f1.in","r",stdin);
  71. #endif
  72.     T=read();
  73.     while(T--) {
  74.     solve();
  75.     }
  76. }

kmp算法

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  8. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  9. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  10. #define MAXN 1000005
  11. //#define ivorysi
  12. using namespace std;
  13. typedef long long ll;
  14. ll read() {
  15.     ll res=0,neg=1;
  16.     char c=getchar();
  17.     while(c<'0' || c>'9') {
  18.     if(c=='-') neg=-1;
  19.     c=getchar();
  20.     }
  21.     while(c>='0' && c<='9') {
  22.     res=res*10+c-'0';
  23.     c=getchar();
  24.     }
  25.     return res*neg;
  26. }
  27. char s[MAXN],t[MAXN];
  28. int lens,lent;
  29. int next[MAXN];
  30. void solve() {
  31.     scanf("%s%s",s+1,t+1);
  32.     lens=strlen(s+1),lent=strlen(t+1);
  33.     next[1]=0;
  34.     siji(i,2,lent) {
  35.     int p=next[i-1];
  36.     while(p>0 && t[p+1]!=t[i]) p=next[p];
  37.     if(t[p+1]==t[i]) next[i]=p+1;
  38.     else next[i]=0;
  39.     }
  40.     int p=0;
  41.     siji(i,1,lens) {
  42.     while(p>0 && t[p+1]!=s[i]) p=next[p];
  43.     if(t[p+1]==s[i]) ++p;
  44.     if(p==lent) {
  45.         p=next[p];
  46.         printf("%d\n",i-lent+1);
  47.     }
  48.     }
  49.     siji(i,1,lent) {
  50.     printf("%d%c",next[i]," \n"[i==lent]);
  51.     }
  52. }
  53. int main() {
  54. #ifdef ivorysi
  55.     freopen("f1.in","r",stdin);
  56. #endif
  57.     solve();
  59. }

Manacher算法

注意转移的时候是2×pos-i

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  8. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  9. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  10. #define MAXN 25000005
  11. //#define ivorysi
  12. using namespace std;
  13. typedef long long ll;
  14. ll read() {
  15.     ll res=0,neg=1;
  16.     char c=getchar();
  17.     while(c<'0' || c>'9') {
  18.     if(c=='-') neg=-1;
  19.     c=getchar();
  20.     }
  21.     while(c>='0' && c<='9') {
  22.     res=res*10+c-'0';
  23.     c=getchar();
  24.     }
  25.     return res*neg;
  26. }
  27. char s[MAXN],t[MAXN*2];
  28. int r[MAXN*2];
  29. int lens,lent,ans;
  30. void solve() {
  31.     scanf("%s",s+1);
  32.     lens=strlen(s+1),lent=strlen(t+1);
  33.     siji(i,1,lens) {
  34.     t[i*2-1]='$';
  35. 	t[i*2]=s[i];
  36.     }
  37.     lent=lens*2+1;
  38.     t[lent]='$';
  39.     int pos=0,maxright=0;
  40.     siji(i,1,lent) {
  41.     r[i]=min(r[2*pos-i],maxright-i+1);
  42.     r[i]=max(r[i],1);
  43.     while(i+r[i]<=lent && i-r[i]>0 && t[i-r[i]]==t[i+r[i]]) ++r[i];
  44.     if(i+r[i]-1>maxright) {
  45.         maxright=i+r[i]-1;
  46.         pos=i;
  47.     }
  48.     ans=max(ans,r[i]-1);
  49.     }
  50.     printf("%d\n",ans);
  51. }
  52. int main() {
  53. #ifdef ivorysi
  54.     freopen("f1.in","r",stdin);
  55. #endif
  56.     solve();
  58. }

欧拉筛法

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  8. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  9. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  10. #define MAXN 10000005
  11. #define mod 1000000007
  12. //#define ivorysi
  13. using namespace std;
  14. typedef long long ll;
  15. ll read() {
  16.     ll res=0,neg=1;
  17.     char c=getchar();
  18.     while(c<'0' || c>'9') {
  19.     if(c=='-') neg=-1;
  20.     c=getchar();
  21.     }
  22.     while(c>='0' && c<='9') {
  23.     res=res*10+c-'0';
  24.     c=getchar();
  25.     }
  26.     return res*neg;
  27. }
  30. int m,n;
  31. int prime[MAXN],cnt;
  32. bool isprime[MAXN];
  33. void solve() {
  34.     n=read();m=read();
  35.     memset(isprime,1,sizeof(isprime));
  36.     isprime[1]=0;
  37.     siji(i,2,n) {
  38.     if(isprime[i]) {
  39.         prime[++cnt]=i;
  40.     }
  41.     siji(j,1,cnt) {
  42.         if(prime[j]>n/i) break;
  43.         isprime[i*prime[j]]=0;
  44.         if(i%prime[j]==0) break;
  45.     }
  46.     }
  47.     int x;
  48.     siji(i,1,m) {
  49.     x=read();
  50.     if(isprime[x]) {
  51.         puts("Yes");
  52.     }
  53.     else {
  54.         puts("No");
  55.     }
  56.     }
  57. }
  58. int main() {
  59. #ifdef ivorysi
  60.     freopen("f1.in","r",stdin);
  61. #endif
  62.     solve();
  63. }

三分法

假如是极大值，如果val(lm) < val(rm)，那么极大值在[l,rm]，否则极大值在[lm,r]

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  8. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  9. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  10. #define MAXN 10000005
  11. #define mod 1000000007
  12. //#define ivorysi
  13. using namespace std;
  14. typedef long long ll;
  15. ll read() {
  16.     ll res=0,neg=1;
  17.     char c=getchar();
  18.     while(c<'0' || c>'9') {
  19.     if(c=='-') neg=-1;
  20.     c=getchar();
  21.     }
  22.     while(c>='0' && c<='9') {
  23.     res=res*10+c-'0';
  24.     c=getchar();
  25.     }
  26.     return res*neg;
  27. }
  28. int n;
  29. double a[15],l,r;
  30. double val(double x) {
  31.     double tmp=1.0,res=0.0;
  32.     siji(i,1,n+1) {
  33.     res+=tmp*a[i];
  34.     tmp=tmp*x;
  35.     }
  36.     return res;
  37. }
  38. void solve() {
  39.     scanf("%d%lf%lf",&n,&l,&r);
  40.     siji(i,1,n+1) {
  41.     scanf("%lf",&a[n-i+2]);
  42.     }
  43.     while(r-l>1e-6) {
  44.     double lm=l+(r-l)/3.0;
  45.     double rm=r-(r-l)/3.0;
  46.     if(val(lm)<val(rm)) l=lm;
  47.     else r=rm;
  48.     }
  49.     printf("%.5lf\n",l);
  50. }
  51. int main() {
  52. #ifdef ivorysi
  53.     freopen("f1.in","r",stdin);
  54. #endif
  55.     solve();
  56. }

Floyd

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  8. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  9. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  10. #define MAXN 10000005
  11. #define mod 1000000007
  12. //#define ivorysi
  13. using namespace std;
  14. typedef long long ll;
  15. ll read() {
  16.     ll res=0,neg=1;
  17.     char c=getchar();
  18.     while(c<'0' || c>'9') {
  19.     if(c=='-') neg=-1;
  20.     c=getchar();
  21.     }
  22.     while(c>='0' && c<='9') {
  23.     res=res*10+c-'0';
  24.     c=getchar();
  25.     }
  26.     return res*neg;
  27. }
  28. int n,q;
  29. ll g[105][105];
  30. void solve() {
  31.     n=read();
  32.     siji(i,1,n) {
  33.     siji(j,1,n) {
  34.         g[i][j]=read();
  35.     }
  36.     }
  37.     siji(k,1,n) {
  38.     siji(i,1,n) {
  39.         siji(j,1,n) {
  40.         g[i][j]=min(g[i][k]+g[k][j],g[i][j]);
  41.         }
  42.     }
  43.     }
  44.     int a,b;
  45.     q=read();
  46.     siji(i,1,q) {
  47.     a=read();b=read();
  48.     printf("%lld\n",g[a][b]);
  49.     }
  50. }
  51. int main() {
  52. #ifdef ivorysi
  53.     freopen("f1.in","r",stdin);
  54. #endif
  55.     solve();
  56. }

线段树优化dijkstra

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  8. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  9. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  10. #define MAXN 10005
  11. #define MAXM 500005
  12. #define mod 1000000007
  13. #define ivorysi
  14. using namespace std;
  15. typedef long long ll;
  16. ll read() {
  17.     ll res=0,neg=1;
  18.     char c=getchar();
  19.     while(c<'0' || c>'9') {
  20.     if(c=='-') neg=-1;
  21.     c=getchar();
  22.     }
  23.     while(c>='0' && c<='9') {
  24.     res=res*10+c-'0';
  25.     c=getchar();
  26.     }
  27.     return res*neg;
  28. }
  29. int n,m,s;
  30. struct node {
  31.     int to,next,val;
  32. }edge[MAXM*2];
  33. int head[MAXN],sumedge;
  34. void add(int u,int v,int c) {
  35.     edge[++sumedge].to=v;
  36.     edge[sumedge].next=head[u];
  37.     edge[sumedge].val=c;
  38.     head[u]=sumedge;
  39. }
  40. ll dis[MAXN],dist[MAXN];
  41. int tr[MAXN*4],pos[MAXN];
  42. bool vis[MAXN];
  43. void build(int u,int l,int r) {
  44.     if(l==r) {
  45.     tr[u]=l;
  46.     pos[l]=u;
  47.     return;
  48.     }
  49.     int m=(l+r)>>1;
  50.     build(u<<1,l,m);
  51.     build(u<<1|1,m+1,r);
  52.     if(dist[tr[u<<1]]<dist[tr[u<<1|1]]) {
  53.     tr[u]=tr[u<<1];
  54.     }
  55.     else {
  56.     tr[u]=tr[u<<1|1];
  57.     }
  58. }
  59. void change(int x) {
  60.     int t=pos[x]>>1;
  61.     while(t>=1) {
  62.     if(dist[tr[t<<1]]<dist[tr[t<<1|1]]) {
  63.         tr[t]=tr[t<<1];
  64.     }
  65.     else {
  66.         tr[t]=tr[t<<1|1];
  67.     }
  68.     t>>=1;
  69.     }
  70. }
  71. void dijkstra(int u) {
  72.     siji(i,1,n) dist[i]=0x7fffffff;
  73.     dist[u]=0;
  74.     build(1,1,n);
  75.     int cnt=n;
  76.     while(cnt--) {
  77.     int now=tr[1];
  78.     dis[now]=dist[now];
  79.     vis[now]=1;
  80.     for(int i=head[now];i;i=edge[i].next) {
  81.         int v=edge[i].to,w=edge[i].val;
  82.         if((!vis[v]) && dist[v]-w>dist[now]) {
  83.         dist[v]=dist[now]+w;
  84.         change(v);
  85.         }
  86.     }
  87.     dist[now]=(ll)0x7fffffff+1;
  88.     change(now);
  89.     }
  90. }
  91. void solve() {
  92.     n=read();m=read();s=read();
  93.     int a,b,c;
  94.     siji(i,1,m) {
  95.     a=read();b=read();c=read();
  96.     add(a,b,c);
  97.     }
  98.     dijkstra(s);
  99.     siji(i,1,n) {
  100.     printf("%lld%c",dis[i]," \n"[i==n]);
  101.     }
  102. }
  103. int main() {
  104. #ifdef ivorysi
  105.     freopen("f1.in","r",stdin);
  106. #endif
  107.     solve();
  108. }

kruskal

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  8. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  9. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  10. #define MAXM 2000005
  11. #define mod 1000000007
  12. //#define ivorysi
  13. using namespace std;
  14. typedef long long ll;
  15. ll read() {
  16.     ll res=0,neg=1;
  17.     char c=getchar();
  18.     while(c<'0' || c>'9') {
  19.     if(c=='-') neg=-1;
  20.     c=getchar();
  21.     }
  22.     while(c>='0' && c<='9') {
  23.     res=res*10+c-'0';
  24.     c=getchar();
  25.     }
  26.     return res*neg;
  27. }
  28. struct node {
  29.     int u,v,val;
  30.     bool operator < (const node &b) {
  31.     return val<b.val;
  32.     }
  33. }edge[MAXM];
  34. int n,m;
  35. int fa[10005];
  36. int getfa(int x) {
  37.     return x==fa[x]?x:fa[x]=getfa(fa[x]);
  38. }
  39. void solve() {
  40.     n=read();m=read();
  41.     int x,y,z;
  42.     siji(i,1,m) {
  43.     x=read();y=read();z=read();
  44.     edge[i].u=x;edge[i].v=y;edge[i].val=z;
  45.     }
  46.     sort(edge+1,edge+m+1);
  47.     siji(i,1,n) {
  48.     fa[i]=i;
  49.     }
  50.     ll ans=0;
  51.     siji(i,1,m) {
  52.     int l=getfa(edge[i].u),z=getfa(edge[i].v);
  53.     if(l!=z) {
  54.         fa[l]=z;
  55.         ans+=edge[i].val;
  56.     }
  57.     }
  58.     printf("%lld\n",ans);
  59. }
  60. int main() {
  61. #ifdef ivorysi
  62.     freopen("f1.in","r",stdin);
  63. #endif
  64.     solve();
  65. }

线段树优化prim

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  8. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  9. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  10. #define MAXM 2000005
  11. #define MAXN 10005
  12. #define mod 1000000007
  13. //#define ivorysi
  14. using namespace std;
  15. typedef long long ll;
  16. ll read() {
  17.     ll res=0,neg=1;
  18.     char c=getchar();
  19.     while(c<'0' || c>'9') {
  20.     if(c=='-') neg=-1;
  21.     c=getchar();
  22.     }
  23.     while(c>='0' && c<='9') {
  24.     res=res*10+c-'0';
  25.     c=getchar();
  26.     }
  27.     return res*neg;
  28. }
  29. struct node {
  30.     int to,next,val;
  31. }edge[MAXM*4];
  32. int head[10005],sumedge;
  33. void add(int u,int v,int c) {
  34.     edge[++sumedge].to=v;
  35.     edge[sumedge].next=head[u];
  36.     edge[sumedge].val=c;
  37.     head[u]=sumedge;
  38. }
  39. bool vis[MAXN];
  40. int n,m,pos[MAXN];
  41. ll dist[MAXN],tr[MAXN*4],ans;
  42. void build(int u,int l,int r) {
  43.     if(l==r) {
  44.     tr[u]=l;
  45.     pos[l]=u;
  46.     return ;
  47.     }
  48.     int m=(l+r)>>1;
  49.     build(u<<1,l,m);
  50.     build(u<<1|1,m+1,r);
  51.     if(dist[tr[u<<1]] < dist[tr[u<<1|1]]) {
  52.     tr[u]=tr[u<<1];
  53.     }
  54.     else {
  55.     tr[u]=tr[u<<1|1];
  56.     }
  57. }
  58. void change(int x) {
  59.     int t=pos[x]>>1;
  60.     while(t>=1) {
  61.     if(dist[tr[t<<1]]<dist[tr[t<<1|1]]) {
  62.         tr[t]=tr[t<<1];
  63.     }
  64.     else {
  65.         tr[t]=tr[t<<1|1];
  66.     }
  67.     t>>=1;
  68.     }
  69. }
  70. void solve() {
  71.     n=read();m=read();
  72.     int x,y,z;
  73.     siji(i,1,m) {
  74.     x=read();y=read();z=read();
  75.     add(x,y,z);add(y,x,z);
  76.     }
  77.     siji(i,1,n) dist[i]=0x7fffffff;
  78.     dist[1]=0;
  79.     build(1,1,n);
  80.     int cnt=n;
  81.     while(cnt--) {
  82.     int u=tr[1];
  83.     vis[u]=1;
  84.     ans+=dist[u];
  85.     for(int i=head[u];i;i=edge[i].next) {
  86.         int v=edge[i].to,w=edge[i].val;
  87.         if((!vis[v]) && dist[v]>w) {
  88.         dist[v]=w;
  89.         change(v);
  90.         }
  91.     }
  92.     dist[u]=0x7fffffff;
  93.     change(u);
  94.     }
  95.     printf("%lld\n",ans);
  96. }
  97. int main() {
  98. #ifdef ivorysi
  99.     freopen("f1.in","r",stdin);
  100. #endif
  101.     solve();
  102. }

判负环

反正都是距离是负的，我们判断每个点都作为出发点，然后初始的dist是0
然后从每个点开始跑spfa_dfs，如果有负环就回溯
回溯的时候可能错过一些vis点的恢复，所以我们要初始化一遍vis

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  8. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  9. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  10. #define MAXN 200005
  11. #define mod 1000000007
  12. //#define ivorysi
  13. using namespace std;
  14. typedef long long ll;
  15. ll read() {
  16.     ll res=0,neg=1;
  17.     char c=getchar();
  18.     while(c<'0' || c>'9') {
  19.     if(c=='-') neg=-1;
  20.     c=getchar();
  21.     }
  22.     while(c>='0' && c<='9') {
  23.     res=res*10+c-'0';
  24.     c=getchar();
  25.     }
  26.     return res*neg;
  27. }
  28. struct node {
  29.     int to,next,val;
  30. }edge[MAXN*4];
  31. int head[MAXN],sumedge,dist[MAXN];
  32. int n,m,T;
  33. void add(int u,int v,int c) {
  34.     edge[++sumedge].to=v;
  35.     edge[sumedge].next=head[u];
  36.     edge[sumedge].val=c;
  37.     head[u]=sumedge;
  38. }
  39. void addtwo(int u,int v,int c) {
  40.     add(u,v,c);
  41.     add(v,u,c);
  42. }
  43. bool vis[MAXN];
  44. bool spfa(int u) {
  45.     vis[u]=1;
  46.     for(int i=head[u];i;i=edge[i].next) {
  47.     int v=edge[i].to,w=edge[i].val;
  48.     if(dist[v]>dist[u]+w) {
  49.         dist[v]=dist[u]+w;
  50.         if(vis[v]) return true;
  51.         else {
  52.         if(spfa(v)) return true;
  53.         }
  54.     }
  55.     }
  56.     vis[u]=0;
  57.     return false;
  58. }
  59. void solve() {
  60.     memset(head,0,sizeof(head));
  61.     //memset(edge,0,sizeof(edge));
  62.     sumedge=0;
  63.     n=read(),m=read();
  64.     int x,y,z;
  65.     siji(i,1,m) {
  66.     x=read(),y=read(),z=read();
  67.     if(z>=0) {
  68.         addtwo(x,y,z);
  69.     }
  70.     else {
  71.         add(x,y,z);
  72.     }
  73.     }
  74.     memset(dist,0,sizeof(dist));
  75.     memset(vis,0,sizeof(vis));
  76.     siji(i,1,n) {
  77.     if(spfa(i)) {
  78.         puts("YE5");
  79.         return;
  80.     }
  81.     }
  82.     puts("N0");
  83. }
  84. int main() {
  85. #ifdef ivorysi
  86.     freopen("f1.in","r",stdin);
  87. #endif
  88.     T=read();
  89.     while(T--) {
  90.     solve();
  91.     }
  92. }

数据结构

并查集

我发现我并不是很会我当年做的这道题了……
NOI的食物链
我们要把所有的对应关系都考虑上
对于每个点建两个虚拟节点
x y如果可以是同类
x的敌人是y的敌人
x的食物是y的食物

x如果可以吃y
x的食物是y
y的敌人是x
x的敌人是y的食物

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  6. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  7. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  8. #define MAXN 100005
  9. //#define ivorysi
  10. using namespace std;
  11. typedef long long ll;
  12. int fa[3*MAXN];
  13. //1-n similar
  14. //n+1-2n its prey
  15. //2n+1-3n its enemy
  16. int n,k;
  17. int ans;
  18. int getfa(int x) {
  19.     return x==fa[x] ? x : fa[x]=getfa(fa[x]);
  20. }
  21. void solve() {
  22.     scanf("%d%d",&n,&k);
  23.     siji(i,1,3*n) {
  24.     fa[i]=i;
  25.     }
  26.     int op,x,y;
  27.     siji(i,1,k) {
  28.     scanf("%d%d%d",&op,&x,&y);
  29.     if(x>n || y>n) {++ans;continue;}
  30.     if(op==1) {
  31.         int p=getfa(x),q=getfa(y);
  32.         if(p==getfa(y+n) || p==getfa(y+2*n)){
  33.         ++ans;
  34.         }
  35.         else {
  36.         fa[q]=p;
  37.         fa[getfa(x+n)]=getfa(y+n);
  38.         fa[getfa(x+2*n)]=getfa(y+2*n);
  39.         }
  40.     }
  41.     else {
  42.         int p=getfa(x);
  43.         if(p==getfa(y) || p==getfa(y+n)) {
  44.         ++ans;
  45.         }
  46.         else {
  47.         fa[getfa(y+2*n)]=getfa(x);
  48.         fa[getfa(x+n)]=getfa(y);
  49.         fa[getfa(x+2*n)]=getfa(y+n);
  50.         }
  51.     }
  52.     }
  53.     printf("%d\n",ans);
  54. }
  55. int main() {
  56. #ifdef ivorysi
  57.     freopen("f1.in","r",stdin);
  58. #endif
  59.     solve();
  60. }

线段树

至今我还是对打标记心怀畏惧……其实标记还可以打很多东西……

4927 线段树练习5

时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold

题目描述 Description

有n个数和5种操作
add a b c：把区间[a,b]内的所有数都增加c
set a b c：把区间[a,b]内的所有数都设为c
sum a b：查询区间[a,b]的区间和
max a b：查询区间[a,b]的最大值
min a b：查询区间[a,b]的最小值

输入描述 Input Description

第一行两个整数n，m，第二行n个整数表示这n个数的初始值
接下来m行操作，同题目描述
输出描述 Output Description
对于所有的sum、max、min询问，一行输出一个答案

样例输入 Sample Input

10 6
3 9 2 8 1 7 5 0 4 6
add 4 9 4
set 2 6 2
add 3 8 2
sum 2 10
max 1 7
min 3 6

样例输出 Sample Output

49
11
4

数据范围及提示 Data Size & Hint

1 < n ,m<=100000

题解

这道题教会我一种新的打标记的方式……
线段树是大家喜闻乐见的RMQ，但是这个东西多了一个整体修改
我们针对整体修改，如果一个区间被整体修改了，那么它的加和的lazy必然也没有用了，如果被整体修改之后再加上加和，我们还需要用到这个lazy，所以我们要设两个开关，一个是整体修改的标记，一个是区间加的标记，如果有整体修改的标记先下放它，然后再判断有区间加的标记再下放
注意不能直接把在有整体修改的时候把区间加直接放到修改上，因为两次的区间也不一定覆盖啊……

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  8. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  9. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  10. #define MAXN 100005
  11. //#define ivorysi
  12. using namespace std;
  13. typedef long long ll;
  14. ll read() {
  15.     ll res=0;
  16.     char c=getchar();
  17.     while(c<'0' || c>'9') c=getchar();
  18.     while(c>='0' && c<='9') {
  19.     res=res*10+c-'0';
  20.     c=getchar();
  21.     }
  22.     return res;
  23. }
  24. struct node {
  25.     int l,r;
  26.     ll minq,maxq,lazy,sum,setq;
  27.     bool iscover,isadd;
  29. }tr[MAXN<<2];
  30. ll a[MAXN];
  31. int n,m;
  32. void build(int u,int l,int r) {
  33.     tr[u].l=l;
  34.     tr[u].r=r;
  35.     if(l==r) {
  36.     tr[u].sum=a[l];
  37.     tr[u].maxq=a[l];
  38.     tr[u].minq=a[l];
  39.     return;
  40.     }
  41.     int m=(l+r)>>1;
  42.     build(u<<1,l,m);
  43.     build(u<<1|1,m+1,r);
  44.     tr[u].minq=min(tr[u<<1].minq,tr[u<<1|1].minq);
  45.     tr[u].maxq=max(tr[u<<1].maxq,tr[u<<1|1].maxq);
  46.     tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
  47. }
  48. void pushnode(int u) {
  49.     if(tr[u].iscover) {
  50.     if(tr[u<<1].l!=tr[u<<1].r) {
  51.         tr[u<<1].lazy=0;tr[u<<1].isadd=0;
  52.         tr[u<<1].iscover=1;
  53.     }
  54.     tr[u<<1].setq=tr[u].setq;
  55.     tr[u<<1].minq=tr[u<<1].maxq=tr[u].setq;
  56.     tr[u<<1].sum=(tr[u<<1].r-tr[u<<1].l+1)*tr[u].setq;
  57.     if(tr[u<<1|1].l!=tr[u<<1|1].r) {
  58.         tr[u<<1|1].lazy=0;tr[u<<1|1].isadd=0;
  59.         tr[u<<1|1].iscover=1;
  60.     }
  61.     tr[u<<1|1].setq=tr[u].setq;
  62.     tr[u<<1|1].minq=tr[u<<1|1].maxq=tr[u].setq;
  63.     tr[u<<1|1].sum=(tr[u<<1|1].r-tr[u<<1|1].l+1)*tr[u].setq;
  64.     tr[u].iscover=0;
  65.     tr[u].setq=0;
  66.     }
  67.     if(tr[u].isadd){
  68.     if(tr[u<<1].l!=tr[u<<1].r) {
  69.         tr[u<<1].isadd=1;
  70.         tr[u<<1].lazy+=tr[u].lazy;
  71.     }
  72.     tr[u<<1].minq+=tr[u].lazy;
  73.     tr[u<<1].maxq+=tr[u].lazy;
  74.     tr[u<<1].sum+=(tr[u<<1].r-tr[u<<1].l+1)*tr[u].lazy;
  75.     if(tr[u<<1|1].l!=tr[u<<1|1].r) {
  76.         tr[u<<1|1].isadd=1;
  77.         tr[u<<1|1].lazy+=tr[u].lazy;
  78.     }
  79.     tr[u<<1|1].minq+=tr[u].lazy;
  80.     tr[u<<1|1].maxq+=tr[u].lazy;
  81.     tr[u<<1|1].sum+=(tr[u<<1|1].r-tr[u<<1|1].l+1)*tr[u].lazy;
  82.     tr[u].lazy=0;tr[u].isadd=0;
  83.     }
  84. }
  85. void update(int u) {
  86.     tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
  87.     tr[u].minq=min(tr[u<<1].minq,tr[u<<1|1].minq);
  88.     tr[u].maxq=max(tr[u<<1].maxq,tr[u<<1|1].maxq);
  89. }
  90. void add(int u,int l,int r,ll x) {
  91.     if(tr[u].l==l && tr[u].r==r) {
  92.     tr[u].isadd=1;
  93.     tr[u].lazy+=x;
  94.     tr[u].minq+=x;
  95.     tr[u].maxq+=x;
  96.     tr[u].sum+=(tr[u].r-tr[u].l+1)*x;
  97.     return;
  98.     }
  99.     pushnode(u);
  100.     int m=(tr[u].l+tr[u].r)>>1;
  101.     if(r<=m) {
  102.     add(u<<1,l,r,x);
  103.     }
  104.     else if(l>m) {
  105.     add(u<<1|1,l,r,x);
  106.     }
  107.     else {
  108.     add(u<<1,l,m,x);
  109.     add(u<<1|1,m+1,r,x);
  110.     }
  111.     update(u);
  112. }
  113. void change(int u,int l,int r,ll c) {
  114.     if(tr[u].l==l && tr[u].r==r) {
  115.     tr[u].lazy=0;
  116.     tr[u].isadd=0;
  117.     tr[u].iscover=1;
  118.     tr[u].setq=c;
  119.     tr[u].minq=tr[u].maxq=c;
  120.     tr[u].sum=(tr[u].r-tr[u].l+1)*c;
  121.     return;
  122.     }
  123.     pushnode(u);
  124.     int m=(tr[u].l+tr[u].r)>>1;
  125.     if(r<=m) {
  126.     change(u<<1,l,r,c);
  127.     }
  128.     else if(l>m) {
  129.     change(u<<1|1,l,r,c);
  130.     }
  131.     else {
  132.     change(u<<1,l,m,c);
  133.     change(u<<1|1,m+1,r,c);
  134.     }
  135.     update(u);
  136. }
  137. ll qmax(int u,int l,int r) {
  138.     if(tr[u].l==l && tr[u].r==r) {
  139.     return tr[u].maxq;
  140.     }
  141.     int m=(tr[u].l+tr[u].r)>>1;
  142.     pushnode(u);
  143.     if(r<=m) {
  144.     return qmax(u<<1,l,r);
  145.     }
  146.     else if(l>m) {
  147.     return qmax(u<<1|1,l,r);
  148.     }
  149.     else {
  150.     return max(qmax(u<<1,l,m),qmax(u<<1|1,m+1,r));
  151.     }
  152.     update(u);
  153. }
  154. ll qmin(int u,int l,int r) {
  155.     if(tr[u].l==l && tr[u].r==r) {
  156.     return tr[u].minq;
  157.     }
  158.     int m=(tr[u].l+tr[u].r)>>1;
  159.     pushnode(u);
  160.     if(r<=m) {
  161.     return qmin(u<<1,l,r);
  162.     }
  163.     else if(l>m) {
  164.     return qmin(u<<1|1,l,r);
  165.     }
  166.     else {
  167.     return min(qmin(u<<1,l,m),qmin(u<<1|1,m+1,r));
  168.     }
  169.     update(u);
  170. }
  171. ll qsum(int u,int l,int r) {
  172.     if(tr[u].l==l && tr[u].r==r) {
  173.     return tr[u].sum;
  174.     }
  175.     int m=(tr[u].l+tr[u].r)>>1;
  176.     pushnode(u);
  177.     if(r<=m) {
  178.     return qsum(u<<1,l,r);
  179.     }
  180.     else if(l>m) {
  181.     return qsum(u<<1|1,l,r);
  182.     }
  183.     else {
  184.     return qsum(u<<1,l,m)+qsum(u<<1|1,m+1,r);
  185.     }
  186.     update(u);
  187. }
  188. char c[15];
  189. void solve() {
  190.     n=read();m=read();
  191.     siji(i,1,n) {
  192.     a[i]=read();
  193.     }
  194.     build(1,1,n);
  195.     int a,b,x;
  196.     siji(i,1,m) {
  197.     scanf("%s",c+1);
  198.     a=read();b=read();
  199.     if(c[1]=='a') {
  200.         x=read();
  201.         add(1,a,b,x);
  202.     }
  203.     else if(c[1]=='s' && c[2]=='e') {
  204.         x=read();
  205.         change(1,a,b,x);
  206.     }
  207.     else if(c[1]=='s' && c[2]=='u') {
  208.         printf("%lld\n",qsum(1,a,b));
  209.     }
  210.     else if(c[1]=='m' && c[2]=='i') {
  211.         printf("%lld\n",qmin(1,a,b));
  212.     }
  213.     else {
  214.         printf("%lld\n",qmax(1,a,b));
  215.     }
  216.     }
  217. }
  218. int main() {
  219.     solve();
  220. }

树状数组

区间修改，区间查询……不过这个题是单点，但是道理一样
我们考虑查分，每个查分的值都乘上整个序列，再删除掉重复的部分，两端分开维护

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  8. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  9. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  10. #define MAXN 500005
  11. //#define ivorysi
  12. using namespace std;
  13. typedef long long ll;
  14. ll read() {
  15.     ll res=0,neg=1;
  16.     char c=getchar();
  17.     while(c<'0' || c>'9') {
  18.     if(c=='-') neg=-1;
  19.     c=getchar();
  20.     }
  21.     while(c>='0' && c<='9') {
  22.     res=res*10+c-'0';
  23.     c=getchar();
  24.     }
  25.     return res*neg;
  26. }
  27. int n,m;
  28. ll a[MAXN],sum[MAXN];
  29. ll tr1[MAXN],tr2[MAXN];
  30. int lowbit(int x) {return x&(-x);}
  31. void change(ll *cur,int pos,ll k) {
  32.     while(pos<=n) {
  33.     cur[pos]+=k;
  34.     pos+=lowbit(pos);
  35.     }
  36. }
  37. ll _query(ll *cur,int pos) {
  38.     ll res=0;
  39.     while(pos>0) {
  40.     res+=cur[pos];
  41.     pos-=lowbit(pos);
  42.     }
  43.     return res;
  44. }
  45. ll query(int pos) {
  46.     ll res=_query(tr1,pos)*pos+_query(tr2,pos)+sum[pos];
  47.     return res;
  48. }
  49. void solve() {
  50.     n=read();m=read();
  51.     siji(i,1,n) {
  52.     a[i]=read();
  53.     sum[i]=sum[i-1]+a[i];
  54.     }
  55.     int op,x,y,k;
  56.     while(m--) {
  57.     op=read();
  58.     if(op==1) {
  59.         x=read();y=read();k=read();
  60.         change(tr1,x,k);
  61.         change(tr1,y+1,-k);
  62.         change(tr2,x,((ll)x-1)*(-k));
  63.         change(tr2,y+1,(ll)y*k);
  64.     }
  65.     else {
  66.         x=read();
  67.         ll ans=query(x)-query(x-1);
  68.         printf("%lld\n",ans);
  69.     }
  70.     }
  71. }
  72. int main() {
  73. #ifdef ivorysi
  74.     freopen("f1.in","r",stdin);
  75. #endif
  76.     solve();
  77. }

ST表

简单易写的RMQ

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  8. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  9. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  10. #define MAXN 1000005
  11. //define ivorysi
  12. using namespace std;
  13. typedef long long ll;
  14. ll read() {
  15.     ll res=0,neg=1;
  16.     char c=getchar();
  17.     while(c<'0' || c>'9') {
  18.     if(c=='-') neg=-1;
  19.     c=getchar();
  20.     }
  21.     while(c>='0' && c<='9') {
  22.     res=res*10+c-'0';
  23.     c=getchar();
  24.     }
  25.     return res*neg;
  26. }
  27. int a[100006];
  28. int n,m;
  29. int st[100006][25];
  30. int log2[100006];
  31. int calc(int c) {
  32.     int l=0;
  33.     while(c) {
  34.     l++;
  35.     c>>=1;
  36.     }
  37.     return l-1;
  38. }
  39. void solve() {
  40.     n=read();
  41.     m=read();
  42.     siji(i,1,n) {
  43.     a[i]=read();
  44.     st[i][0]=a[i];
  45.     log2[i]=calc(i);
  46.     }
  47.     siji(j,1,20) {
  48.     siji(i,1,n) {
  49.         if((i+(1<<j)-1)>n) break;
  50.         st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
  51.     }
  52.     }
  53.     int a,b;
  54.     siji(i,1,m) {
  55.     a=read();b=read();
  56.     int len=log2[b-a+1];
  57.     int ans=max(st[a][len],st[b-(1<<len)+1][len]);
  58.     printf("%d\n",ans);
  59.     }
  60. }
  61. int main() {
  62. #ifdef ivorysi
  63.     freopen("f1.in","r",stdin);
  64. #endif
  65.     solve();
  67. }

题目描述

如题，已知一个数列，你需要进行下面两种操作：
1.将某区间每一个数加上x
2.将某区间每一个数乘上x
3.求出某区间每一个数的和

输入输出格式

输入格式：

第一行包含三个整数N、M、P，分别表示该数列数字的个数、操作的总个数和模数。
第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。
接下来M行每行包含3或4个整数，表示一个操作，具体如下：
操作1： 格式：1 x y k 含义：将区间[x,y]内每个数乘上k
操作2： 格式：2 x y k 含义：将区间[x,y]内每个数加上k
操作3： 格式：3 x y 含义：输出区间[x,y]内每个数的和对P取模所得的结果

输出格式：

输出包含若干行整数，即为所有操作3的结果。

输入输出样例

输入样例#1：

5 5 38
1 5 4 2 3
2 1 4 1
3 2 5
1 2 4 2
2 3 5 5
3 1 4

输出样例#1：

17
2

说明

时空限制：1000ms,128M
数据规模：
对于30%的数据：N<=8，M<=10
对于70%的数据：N<=1000，M<=10000
对于100%的数据：N<=100000，M<=100000

题解

我们要维护两个标记，一个是乘的标记mul，一个是加的标记add
更新乘法的时候需要用add×mul mul*mul
然后更新加法的时候add+add
pushnode的时候乘法标记直接相乘
加法标记乘上乘法标记再加上加法标记

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  8. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  9. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  10. #define MAXN 100005
  11. #define mod 1000000007
  12. //#define ivorysi
  13. using namespace std;
  14. typedef long long ll;
  15. ll read() {
  16.     ll res=0,neg=1;
  17.     char c=getchar();
  18.     while(c<'0' || c>'9') {
  19.     if(c=='-') neg=-1;
  20.     c=getchar();
  21.     }
  22.     while(c>='0' && c<='9') {
  23.     res=res*10+c-'0';
  24.     c=getchar();
  25.     }
  26.     return res*neg;
  27. }
  28. int n;
  29. ll a[MAXN],m,P;
  30. struct node {
  31.     ll add,mul,sum;
  32.     int l,r;
  33. }tr[MAXN*8];
  34. void update(int u) {
  35.     tr[u].sum=(tr[u<<1].sum+tr[u<<1|1].sum)%P;
  36. }
  37. void build(int u,int l,int r) {
  38.     tr[u].l=l;
  39.     tr[u].r=r;
  40.     tr[u].mul=1;
  41.     tr[u].add=0;
  42.     if(l==r) {
  43.     tr[u].sum=a[l];
  44.     return;
  45.     }
  46.     int mid=(l+r)>>1;
  47.     build(u<<1,l,mid);
  48.     build(u<<1|1,mid+1,r);
  49.     update(u);
  50. }
  51. void push_down(int u) {
  52.     int l=tr[u].l,r=tr[u].r;
  53.     tr[u<<1].sum=tr[u<<1].sum*tr[u].mul%P;
  54.     tr[u<<1|1].sum=tr[u<<1|1].sum*tr[u].mul%P;
  55.     tr[u<<1].mul*=tr[u].mul;
  56.     tr[u<<1].mul%=P;
  57.     tr[u<<1|1].mul*=tr[u].mul;
  58.     tr[u<<1|1].mul%=P;
  59.     int mid=(tr[u].l+tr[u].r)>>1;
  60.     tr[u<<1].sum=(tr[u<<1].sum+tr[u].add*(mid-l+1)%P)%P;
  61.     tr[u<<1|1].sum=(tr[u<<1|1].sum+tr[u].add*(r-mid)%P)%P;
  62.     tr[u<<1].add=(tr[u<<1].add*tr[u].mul%P+tr[u].add)%P;
  63.     tr[u<<1|1].add=(tr[u<<1|1].add*tr[u].mul%P+tr[u].add)%P;
  64.     tr[u].mul=1;tr[u].add=0;
  65. }
  66. void change(int u,int ql,int qr,ll k,bool is_mul) {
  67.     if(ql==tr[u].l && qr==tr[u].r) {
  68.     if(is_mul) {
  69.         tr[u].add=tr[u].add*k%P;
  70.         tr[u].mul=tr[u].mul*k%P;
  71.         tr[u].sum=tr[u].sum*k%P;
  72.     }
  73.     else {
  74.         tr[u].add=(tr[u].add+k)%P;
  75.         tr[u].sum=(tr[u].sum+(tr[u].r-tr[u].l+1)*k%P)%P;
  76.     }
  77.     return;
  78.     }
  79.     push_down(u);
  80.     int mid=(tr[u].l+tr[u].r)>>1;
  81.     if(qr<=mid) {
  82.     change(u<<1,ql,qr,k,is_mul);
  83.     }
  84.     else if(ql>mid) {
  85.     change(u<<1|1,ql,qr,k,is_mul);
  86.     }
  87.     else {
  88.     change(u<<1,ql,mid,k,is_mul);
  89.     change(u<<1|1,mid+1,qr,k,is_mul);
  90.     }
  91.     update(u);
  92. }
  93. ll query(int u,int ql,int qr) {
  94.     if(tr[u].l==ql && tr[u].r==qr) {
  95.     return tr[u].sum;
  96.     }
  97.     push_down(u);
  98.     int mid=(tr[u].l+tr[u].r)>>1;
  99.     if(qr<=mid) {
  100.     return query(u<<1,ql,qr);
  101.     }
  102.     else if(ql>mid) {
  103.     return query(u<<1|1,ql,qr);
  104.     }
  105.     else {
  106.     return (query(u<<1,ql,mid)+query(u<<1|1,mid+1,qr))%P;
  107.     }
  108. }
  109. void solve() {
  110.     n=read();m=read();P=read();
  111.     siji(i,1,n) a[i]=read();
  112.     build(1,1,n);
  113.     ll x,y,k,op;
  114.     siji(i,1,m) {
  115.     op=read();
  116.     x=read();y=read();
  117.     if(op==1) {
  118.         k=read();
  119.         change(1,x,y,k,1);
  120.     }
  121.     else if(op==2) {
  122.         k=read();
  123.         change(1,x,y,k,0);
  124.     }
  125.     else {
  126.         ll res=query(1,x,y);
  127.         printf("%lld\n",res);
  128.     }
  129.     }
  130. }
  131. int main() {
  132. #ifdef ivorysi
  133.     freopen("f1.in","r",stdin);
  134. #endif
  135.     solve();
  136. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注