目录
输入输出
inline int read(){
int s = 0, w = 1;
char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
return s * w;
}
数据结构
线段树
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll mod=1000000007;
const ll N=50010;
ll ans[N];
struct node
{
ll l,r,v,lazy;
}node[N<<2]; // 线段树的空间大概是数组空间的4倍；
void build(ll l,ll r,ll numb) // 线段树的建立；
{
node[numb].l=l;
node[numb].r=r;
node[numb].v=0;
node[numb].lazy=0; // 用了lazy思想，提高了效率；
if(l==r) return;
ll mid=(l+r)>>1;
build(l,mid,numb<<1);
build(mid+1,r,numb<<1|1);
}
void PushUp(ll numb) // 往上往父节点方向更新数据；但是这里不是左右儿子的和，而是最大值，因为是站台人数；
{
node[numb].v=((node[numb<<1].v%mod)*(node[numb<<1|1].v%mod))%mod;
}
void PushDown(ll numb) // 向下往左右儿子方向更新数据；
{
node[numb<<1].lazy+=node[numb].lazy;
node[numb<<1|1].lazy+=node[numb].lazy;
node[numb<<1].v+=node[numb].lazy;
node[numb<<1|1].v+=node[numb].lazy;
node[numb].lazy=0; // 更新完了要清零；
}
void Insert(ll l,ll r,ll numb,ll v) // 插入更新数据；
{
if(node[numb].l==l&&node[numb].r==r) // 如果区间完全重合，则不需要再往下更新了，先保存起来，可以节约很多的时间（lazy思想）
{
node[numb].v=v%mod;
node[numb].lazy+=1;
return;
}
if(node[numb].lazy) PushDown(numb); // 因为没有找到完全重合的区间，所以要先更新下一层区间；
ll mid=(node[numb].r+node[numb].l)>>1;
if(l>mid) Insert(l,r,numb<<1|1,v);
else if(r<=mid) Insert(l,r,numb<<1,v);
else{
Insert(l,mid,numb<<1,v);
Insert(mid+1,r,numb<<1|1,v);
}
PushUp(numb); // 最后还得往上返回，更新父节点区间；
}
ll query(ll l,ll r,ll numb) // 查询区间l到r；
{
if(node[numb].l==l&&node[numb].r==r){
return node[numb].v%mod;
}
//if(node[numb].lazy) PushDown(numb); // 道理同48行；
ll mid=(node[numb].r+node[numb].l)>>1;
if(l>mid) return query(l,r,numb<<1|1)%mod;
else if(r<=mid) return query(l,r,numb<<1)%mod;
else{
return ((query(l,mid,numb<<1)%mod)*(query(mid+1,r,numb<<1|1)%mod)%mod); // 道理同28行；
}
}
ll t,n,k;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>t;
while(t--){
build(1,50000,1);
cin>>n;
for(int i=1;i<=n;++i){
cin>>ans[i];
Insert(i,i,1,ans[i]);
}
cin>>k;
for(int i=0;i<k;++i){
int c,l,r;
cin>>c;
if(c==0){
cin>>l>>r;
cout<<query(l,r,1)<<"
";
}
if(c==1){
cin>>l>>r;
Insert(l,l,1,r);
}
}
}
return 0;
}
主席树
- 非结构体
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int N=100000;
int a[N+10],b[N+10];
int t,m,n,q,p,tot;
int ls[N*30],rs[N*30],sum[N*30],root[N*30];
void build(int &now,int l,int r)
{
now=++tot,sum[now]=0;
if(l==r) return;
int mid=(l+r)>>1;
build(ls[now],l,mid);
build(rs[now],mid+1,r);
}
int update(int lastRoot,int l,int r)
{
int newRoot=++tot;
ls[newRoot]=ls[lastRoot],rs[newRoot]=rs[lastRoot],sum[newRoot]=sum[lastRoot]+1;
if(l==r) return newRoot;
int mid=(r+l)>>1;
if(mid>=p) ls[newRoot]=update(ls[newRoot],l,mid);
else rs[newRoot]=update(rs[newRoot],mid+1,r);
return newRoot;
}
int query(int u,int v,int l,int r,int k)
{
int mid=(r+l)>>1;
int x=sum[ls[v]]-sum[ls[u]];
if(l==r) return l;
if(x>=k) return query(ls[u],ls[v],l,mid,k);
else return query(rs[u],rs[v],mid+1,r,k-x);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>t;
while(t--){
tot=0;
cin>>n>>m;
for(int i=1;i<=n;++i){
cin>>a[i];
b[i]=a[i];
}
sort(b+1,b+1+n);
q=unique(b+1,b+1+n)-b-1;
build(root[0],1,q);
for(int i=1;i<=n;++i){
p=lower_bound(b+1,b+1+q,a[i])-b;
root[i]=update(root[i-1],1,q);
}
for(int i=0;i<m;++i){
int l,r,k;
cin>>l>>r>>k;
cout<<b[query(root[l-1],root[r],1,q,k)]<<"
";
}
}
return 0;
}
- 结构体
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int N=100000;
int t,n,m,q,mid;
ll x;
int a[N+10],b[N+10],root[N*30];
inline int read(){
int s = 0, w = 1;
char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
return s * w;
}
struct treeNode{
ll sum;
int ls,rs;
};
struct chairmanTree{
int tot;//记录最新的根节点索引
treeNode tree[N*30];
void build(int &now,int l,int r)
{
now=++tot;
tree[now].sum=0;
if(l==r) return;
int mid=(l+r)>>1;
build(tree[now].ls,l,mid);
build(tree[now].rs,mid+1,r);
}
int update(int lastRoot,int l,int r,int p)//lastNode->前一个根节点 p->更新的数字在数组中Kth
{
int newRoot=++tot;
tree[newRoot].ls=tree[lastRoot].ls;//连接左子树
tree[newRoot].rs=tree[lastRoot].rs;//连接右子树
tree[newRoot].sum=tree[lastRoot].sum+1;//更新sum
if(l==r){
return newRoot;
}
int mid=(r+l)>>1;
if(mid >= p){
tree[newRoot].ls=update(tree[newRoot].ls,l,mid,p);//更新左子树，新建一个左子树
}else{
tree[newRoot].rs=update(tree[newRoot].rs,mid+1,r,p);
}
return newRoot;
}
int query(int u,int v,int l,int r,int k)//u、v为两棵线段树当前节点编号，相减就是询问区间
{
mid=(l+r)>>1;
x=tree[tree[v].ls].sum-tree[tree[u].ls].sum;
if(l==r)
return r;//或者return l也可以，但是l和1太像了
if(x>=k)
return query(tree[u].ls,tree[v].ls,l,mid,k);
else
return query(tree[u].rs,tree[v].rs,mid+1,r,k-x);
}
}T;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
//t=read();
//while(t--){
int p=0;
T.tot=0,q=0;
memset(root,0,sizeof(root));
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
//cin>>n>>m;
n=read(),m=read();
for(int i=1;i<=n;++i){
//cin>>a[i];
a[i]=read();
b[i]=a[i];
}
sort(b+1,b+1+n);
q=unique(b+1,b+1+n)-b-1;
T.build(root[0],1,q);
for(int i=1;i<=n;++i){
p=lower_bound(b+1,b+1+q,a[i])-b;
root[i]=T.update(root[i-1],1,q,p);
}
while(m--){
int l,r,k;
//cin>>l>>r>>k;
l=read(),r=read(),k=read();
//cout<<b[T.query(root[l-1],root[r],1,q,k)]<<"
";
printf("%d
",b[T.query(root[l-1],root[r],1,q,k)]);
}
//}
return 0;
}
树状数组
图论
最短路
dijkstra
#include<bits/stdc++.h>
using namespace std;
const int INF = 1e6;
const int NUM = 105;
struct edge{
int from, to, w;
edge(int a, int b, int c){from=a, to=b, w=c;}
};
vector<edge>e[MUN];
struct s_node{
int id,n_dis;
s_node(int b, int c){id = b; n_dis = c;}
bool operator < (const s_node & a) const {
return n_dis > a.n_dis;
}
};
int n,m;
int pre[NUM];
void print_path(int s,int t){
if(s==t){
printf("%d ",s);
return;
}
print_path(s,pre[t]);
printf("%d ",t);
}
void dijkstra()
{
int s=1;
int dis[NUM];
bool done[NUM];
for(int i=1;i<=n;++i){
dis[i]=INF;
done[i]=false;
}
dis[s]=0;
priority_queue<s_node>Q;
Q.push(s_node(s,dis[s]));
while(!Q.empty()){
s_node u=Q.top();
Q.pop();
if(done[u.id])
continue;
done[u.id]=true;
for(int i=0;i<e[u.id].size();++i){
edge y=e[u.id][i];
if(done[y.to])
continue;
if(dis[y.to]>y.w+u.n_dis){
dis[y.to]=y.w+u.n_dis;
Q.push(s_node(y.to,dis[y.to]));
pre[y.to]=u.id;
}
}
}
printf("%d
",dis[n]);
//print_path(s,n);
}
int main()
{
while(~scanf("%d%d",&n,&m)){
if(n==0&&m==0) return 0;
for(int i=1;i<=n;++i){
e[i].clear();
}
while(m--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
e[a].push_back(edge(a,b,c));
e[b].push_back(edge(b,a,c));
}
dijkstra();
}
}
spfa
#include<bits/stdc++.h>
using namespace std;
const int INF=INT32_MAX/10;
const int NUM=1000005;
struct Edge{
int to,next,w;
}edge[NUM];
int n,m,cnt;
int head[NUM];
int dis[NUM];
bool inq[NUM];
int Neg[NUM];
int pre[NUM];
void print_paht(int s,int t){
;
}
void init()
{
for(int i=0;i<NUM;++i){
edge[i].next=-1;
head[i]=-1;
}
cnt=0;
}
void addedge(int u,int v,int w)
{
edge[cnt].to=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt++;
}
int spfa(int s)
{
memset(Neg,0,sizeof(Neg));
Neg[s]=1;
for(int i=1;i<=n;++i){
dis[i]=INF;
inq[i]=false;
}
dis[s]=0;
queue<int>Q;
Q.push(s);
inq[s]=true;
while(!Q.empty()){
int u=Q.front();
Q.pop();
inq[u]=false;
for(int i=head[u];~i;i=edge[i].next){
int v=edge[i].to, w=edge[i].w;
if(dis[u]+w<dis[v]){
dis[v]=dis[u]+w;
pre[v]=u ;
if(!inq[v]){
inq[v]=true;
Q.push(v);
Neg[v]++;
if(Neg[v]>n) return 1;
}
}
}
}
printf("%d
",dis[n]);
//print_path(s,n);
return 0;
}
int main()
{
while(~scanf("%d%d",&n,&m)){
init();
if(n==0&&m==0) return 0;
while(m--){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w);
addedge(v,u,w);
}
spfa(1);
}
return 0;
}
floye-warshall
#include<bits/stdc++.h>
using namespace std;
const int INF=1e6;
const int NUM=105;
int graph[NUM][NUM];
int n,m;
void floyd()
{
int s=1;
for(int k=1;k<=n;++k){
for(int i=1;i<=n;++i){
if(graph[i][k]!=INF){
for(int j=1;j<=n;j++){
if(graph[i][j]>graph[i][k]+graph[k][j])
graph[i][j]=graph[i][k]+graph[k][j];
}
}
}
}
printf("%d
",graph[s][n]);
}
int main()
{
while(~scanf("%d%d",&n,&m)){
if(n==0&&m==0) return 0;
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j)
graph[i][j]=INF;
}
while(m--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
graph[a][b]=graph[b][c]=c;
}
floyd();
}
return 0;
}
LCA
倍增
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e4+7;
vector<int> v[maxn], w[maxn];
int fa[maxn][31], cost[maxn][31], dep[maxn];
int n, m;
int a, b, c;
void dfs(int root, int fno)//fno->父节点
{
fa[root][0] = fno;
dep[root] = dep[fa[root][0]] + 1;
for (int i = 1; i < 31; ++i) {
fa[root][i] = fa[fa[root][i-1]][i-1];
cost[root][i] = cost[fa[root][i-1]][i-1] + cost[root][i-1];
}
int sz = v[root].size();
for (int i = 0; i < sz; ++i) {
if (v[root][i] == fno) continue;
cost[v[root][i]][0] = w[root][i]; //初始化每个结点的cost
dfs(v[root][i], root);
}
}
int lca(int x, int y)
{
if(dep[x] > dep[y]) swap(x, y);
int tmp = dep[y] - dep[x], ans = 0;
for (int j =0; tmp; ++j, tmp >>= 1)
if (tmp & 1) ans +=cost[y][j], y = fa[y][j];
if(y == x) return ans;
for (int j = 30; j >=0 && y != x; --j) {
if(fa[x][j] != fa[y][j]) {
ans += cost[x][j] + cost[y][j];
x = fa[x][j];
y = fa[y][j];
}
}
ans += cost[x][0] + cost[y][0];
return ans;
}
int main()
{
memset(fa, 0, sizeof(fa));
memset(cost, 0, sizeof(cost));
memset(dep, 0, sizeof(dep));
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d%d%d", &a, &b, &c);
// ++a, ++b;
v[a].push_back(b);
v[b].push_back(a);
w[a].push_back(c);
w[b].push_back(c);
}
dfs(1,0);
scanf("%d", &m);
for (int i = 0; i < m; ++i) {
scanf("%d%d", &a, &b);
// ++a, ++b;
printf("%d
", lca(a, b));
}
return 0;
}
树分治
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e4 + 10;
const int inf = 2e9;
int n, m, a, b, c, rt;
int q[maxn], siz[maxn], maxx[maxn], dist[maxn];
int cur, h[maxn], nxt[maxn], p[maxn], w[maxn];
bool tf[10000010], ret[maxn], vis[maxn];
void add_edge(int x, int y, int z)
{
cur++; //cur -> tot
nxt[cur] = h[x];
h[x] = cur;
p[cur] = y;
w[cur] = z;
}
int sum;
void calcsiz(int x, int fa)// 找重心
{
siz[x] = 1;
maxx[x] = 0;
for (int j = h[x]; j; j = nxt[j]) {
if (p[j] != fa && !vis[p[j]]) {
calcsiz(p[j], x);
maxx[x] = max(maxx[x], siz[p[j]]);
siz[x] += siz[p[j]];
}
}
maxx[x] = max(maxx[x], sum - siz[x]);
if(maxx[x] < maxx[rt]) rt = x;
}
queue<int> tag;
int dd[maxn], cnt;
void calcdist(int x, int fa)
{
dd[++cnt] = dist[x];
for (int j = h[x]; j; j = nxt[j])
if (p[j] != fa && !vis[p[j]])
dist[p[j]] = dist[x] + w[j], calcdist(p[j], x);
}
void dfz(int x, int fa)
{
tf[0] = true;
tag.push(0);
vis[x] = true;
for (int j = h[x]; j; j = nxt[j]) {
if (p[j] != fa && !vis[p[j]]) {
dist[p[j]] = w[j];
calcdist(p[j], x);
for (int k = 1; k <= cnt; ++k) {
for (int i = 1; i <= m ; ++i){
if( q[i] >= dd[k])
ret[i] |= tf[q[i] - dd[k]];
}
}
for (int k = 1; k <= cnt; ++k)
if (dd[k] < 10000010)
tag.push(dd[k]), tf[dd[k]] = true;
cnt = 0;
}
}
while (!tag.empty())
tf[tag.front()] = false, tag.pop();
for (int j = h[x]; j; j = nxt[j]) {
if (p[j] !=fa && !vis[p[j]]) {
sum = siz[p[j]];
rt = 0;
maxx[rt] = inf;
calcsiz(p[j], x);
calcsiz(rt, -1);
dfz(rt, x);
}
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i < n; ++i)
scanf("%d%d%d", &a, &b, &c), add_edge(a, b, c), add_edge(b, a, c);
for (int i = 1; i <= m; ++i)
scanf("%d", q + 1);
rt = 0;
maxx[rt] = inf;
sum = n;
calcsiz(1, -1);// 寻找重心
calcsiz(rt, -1);
dfz(rt, -1);
}
树的重心
// 这份代码默认节点编号从 1 开始，即 i ∈ [1,n]
int size[MAXN], // 这个节点的“大小”（所有子树上节点数 + 该节点）
weight[MAXN], // 这个节点的“重量”
centroid[2]; // 用于记录树的重心（存的是节点编号）
void GetCentroid(int cur, int fa) { // cur 表示当前节点 (current)
size[cur] = 1;
weight[cur] = 0;
for (int i = head[cur]; i != -1; i = e[i].nxt) {
if (e[i].to != fa) { // e[i].to 表示这条有向边所通向的节点。
GetCentroid(e[i].to, cur);
size[cur] += size[e[i].to];
weight[cur] = max(weight[cur], size[e[i].to]);
}
}
weight[cur] = max(weight[cur], n - size[cur]);
if (weight[cur] <= n / 2) { // 依照树的重心的定义统计
centroid[centroid[0] != 0] = cur;
}
}
字符串
KMP
-
最初kmp模板
-
#include<bits/stdc++.h> using namespace std; const int maxn=1e3+5; char s[maxn],p[maxn]; int Next[maxn]; int cnt; void getFail() { Next[0]=0,Next[1]=0; for(int i=1;i<strlen(p)-1;++i){ int j=Next[i]; while(j && p[i]!=p[j]) j=Next[j]; Next[i+1]=p[i]==p[j]?j+1:0; } } void kmp() { int m=strlen(p); int last=-1; int slen=strlen(s),plen=strlen(p); getFail(); int j=0; for(int i=0;i<slen;++i){ while(j && s[i]!=p[j]) j=Next[j]; if(s[i]==p[j]) j++; if(j==m) printf("%d",i-m+1); } } int main() { ios::sync_with_stdio(false); cin>>s>>p; kmp(); return 0; } -
next数组获取函数
-
void GetNext(char *p, int *next)// 模式串 { int plen = strlen(p) ; next[0] = -1 ; int k = -1 ; int j = 0 ; while(j< plen-1) { // p[k]表示前缀 , p[j]表示后缀 ; if(k==-1 || p[j] == p[k]) { k++; j++; next[j] = k ; } else { k = next[k] ; } } } -
优化next函数
-
void GetNextval(char* p, int next[]) { int pLen = strlen(p); next[0] = -1; int k = -1; int j = 0; while (j < pLen ) { //p[k]表示前缀，p[j]表示后缀 if (k == -1 || p[j] == p[k]) { j++; k++; //较之前next数组求法，改动在下面4行 if (p[j] != p[k]) next[j] = k; //之前只有这一行 else //因为不能出现p[j] = p[ next[j ]]，所以当出现时需要继续递归，k = next[k] = next[next[k]] next[j] = next[k]; } else { k = next[k]; } } } -
exkmp
-
#include<bits/stdc++.h> using namespace std; char p[10005],s[1000005]; int next[100005],extend[1000005]; void getNext(char *p, int &plen, int *nexts) { int a = 0,k = 0; nexts[0] = plen; for (int i = 1;i < plen; i++) { if (i >= k || i + nexts[i-1] >= k) { if (i >= k) k = i; while (k <plen && p[k] == p[k-i]) k++; nexts[i] = k - i; a = i; } else nexts[i] = nexts[i - a]; } } void extendkmp (char *s, int &slen, char *p, int &plen, int *extend, int *next) { int a = 0, k = 0; getNext (p, plen, next); for (int i = 0; i < slen; i++) { if (i >=k || i +enxts[i - a] >= k) { if (i >= k) k = i; while (k <slen && k - i < plen && s[k] == p[k -i]) k ++; exten[i] = k - i; a = i; } else extend[i] = nexts[i - a]; } } int main() { int slen, plen; while (cin >> s >>p) { slen = strlen(s); plen = strlen(p); extendkmp(s, slen, p, plen, extend, nexts); cou << "next: "; for (int i = 0; i < plen; ++i) cout << nexts[i] << " "; cout <<" extend: "; for (int i = 0; i < slen; ++i) cout << extend[i] << " "; cout <<" "; } return 0; }字符串hash
-
自然溢出hash
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
ull base=131;
ull a[10010];
char s[10010];
int n,ans=1;
ull hashs(char s[])
{
int len=strlen(s);
ull ans=0;
for (int i=0;i<len;i++)
ans=ans*base+(ull)s[i];
return ans&0x7fffffff;
}
main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%s",s);
a[i]=hashs(s);
}
sort(a+1,a+n+1);
for (int i=2;i<=n;i++)
if (a[i]!=a[i-1])
ans++;
printf("%d
",ans);
}
- 最稳妥的办法是选择两个10^9级别的质数，只有模这两个数都相等才判断相等，但常数略大，代码相对难写，目前暂时没有办法卡掉这种写法（除了卡时间让它超时）
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
ull base=131;
struct data
{
ull x,y;
}a[10010];
char s[10010];
int n,ans=1;
ull mod1=19260817;
ull mod2=19660813;
ull hash1(char s[])
{
int len=strlen(s);
ull ans=0;
for (int i=0;i<len;i++)
ans=(ans*base+(ull)s[i])%mod1;
return ans;
}
ull hash2(char s[])
{
int len=strlen(s);
ull ans=0;
for (int i=0;i<len;i++)
ans=(ans*base+(ull)s[i])%mod2;
return ans;
}
bool comp(data a,data b)
{
return a.x<b.x;
}
main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
scanf("%s",s);
a[i].x=hash1(s);
a[i].y=hash2(s);
}
sort(a+1,a+n+1,comp);
for (int i=2;i<=n;i++)
if (a[i].x!=a[i-1].x || a[i-1].y!=a[i].y)
ans++;
printf("%d
",ans);
}
-
如果能背过或在考场上找出一个10^18级别的质数(Miller-Rabin)，也相对靠谱，主要用于前一种担心会超时
这是只用一个10^18质数的hash(100)
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef unsigned long long ull; ull base=131; ull a[10010]; char s[10010]; int n,ans=1; ull mod=212370440130137957ll;//是质数！！ ull hashs(char s[]) { int len=strlen(s); ull ans=0; for (int i=0;i<len;i++) ans=(ans*base+(ull)s[i])%mod; return ans; } main() { scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%s",s); a[i]=hashs(s); } sort(a+1,a+n+1); for (int i=2;i<=n;i++) if (a[i]!=a[i-1]) ans++; printf("%d ",ans); }
二分
while(l<=r)
{
int mid=(l+r)/2;//min=l+(r-l)/2 防止数据溢出
if(check(mid))
l=mid+1;
else
r=mid-1;
}
//最大值最小答案是l，最小值最大答案是r
下面扒了别人的一篇博客
最大化最小值（二分值最小越小越容易满足条件，求最大值）
区间长度为1时的写法：
解的范围为
// 计算区间为[lb, rb]
while( rb > lb ) // 区间长度为1时终止循环
{
// 防止溢出
int m = lb + (rb - lb + 1) / 2; // 由于是区间长度为1时终止循环，所以要加1
if( ok(m) ) lb = m;
else rb = m - 1;
}
// 跳出循环时 lb == rb
区间长度为2时的写法：
解的范围为
while( rb - lb > 1 ) // 区间长度为2时终止循环
{
// 防止溢出
int m = lb + (rb - lb) / 2; // 由于是区间长度为2时终止循环，所以不用加1（不会死循环）
if( ok(m) ) lb = m;
else rb = m;
}
// 跳出循环时 lb + 1 == rb
// 答案为 lb
最小化最大值（二分值越大越容易满足条件，求最小值）
区间长度为1时的写法：
解的范围为
while( rb > lb )
{
// 防止溢出
int m = lb + (rb - lb) / 2; // 这里虽然区间长度为1，但不需要加1（不会死循环）
if( ok(m) ) rb = m;
else lb = m + 1;
}
// 跳出循环时 lb == rb
区间长度为2时的写法：
解的范围为
while( rb - lb > 1 )
{
// 防止溢出
int m = lb + (rb - lb) / 2;
if( ok(m) ) rb = m;
else lb = m;
}
// 跳出循环时 lb + 1 == rb
// 答案为 rb
浮点数的二分，100次循环可以达到2-100(约为10-30)的精度范围
以最大化最小值为例（即小于该数的解均满足条件）
for( int i = 0; i < 100; ++ i )
{
double m = (lb + rb) / 2;
if(check(m)) lb=m;
else rb=m;
}
// 跳出循环时 lb 与 rb 近似相等，所以都可作为答案
数学
数论
费马小定理
LL ksm(LL x,LL y){
LL ret=1;
while(y){
if(y&1)ret=ret*x%mod;
x=x*x%mod;
y>>=1;
}
return ret;
}
lucas
LL C(LL n,LL m){
if(m>n)return 0;
LL s1=1,s2=1;
for(LL i=n-m+1;i<=n;i++)s1=s1*i%mod;
for(LL i=1;i<=m;i++)s2=s2*i%mod;
return s1*ksm(s2,mod-2);
}
LL Lucas(LL n,LL m){
if(!m)return 1;
return C(n%mod,m%mod)*Lucas(n/mod,m/mod)%mod;
}
Pallard's Rho 大数质因数分解
#include<iostream>
#include<ctime>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;
map<ll, int>m;
const int mod = 10000019;
const int times = 50;//测试50次
ll mul(ll a, ll b, ll m)
//求a*b%m
{
ll ans = 0;
a %= m;
while(b)
{
if(b & 1)ans = (ans + a) % m;
b /= 2;
a = (a + a) % m;
}
return ans;
}
ll pow(ll a, ll b, ll m)
//a^b % m
{
ll ans = 1;
a %= m;
while(b)
{
if(b & 1)ans = mul(a, ans, m);
b /= 2;
a = mul(a, a, m);
}
ans %= m;
return ans;
}
bool Miller_Rabin(ll n, int repeat)//n是测试的大数，repeat是测试重复次数
{
if(n == 2 || n == 3)return true;//特判
if(n % 2 == 0 || n == 1)return false;//偶数和1
//将n-1分解成2^s*d
ll d = n - 1;
int s = 0;
while(!(d & 1)) ++s, d >>= 1;
//srand((unsigned)time(NULL));在最开始调用即可
for(int i = 0; i < repeat; i++)//重复repeat次
{
ll a = rand() % (n - 3) + 2;//取一个随机数,[2,n-1)
ll x = pow(a, d, n);
ll y = 0;
for(int j = 0; j < s; j++)
{
y = mul(x, x, n);
if(y == 1 && x != 1 && x != (n - 1))return false;
x = y;
}
if(y != 1)return false;//费马小定理
}
return true;
}
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
ll pollard_rho(ll n, ll c)//找到n的一个因子
{
ll x = rand() % (n - 2) + 1;
ll y = x, i = 1, k = 2;
while(1)
{
i++;
x = (mul(x, x, n) + c) + n;//不断调整x2
ll d = gcd(y - x, n);
if(1 < d && d < n)
return d;//找到因子
if(y == x)
return n;//找到循环，返回n，重新来
if(i == k)//一个优化
{
y = x;
k <<= 1;
}
}
}
void Find(ll n, ll c)
{
if(n == 1)return;//递归出口
if(Miller_Rabin(n, times))//如果是素数，就加入
{
m[n]++;
return;
}
ll p = n;
while(p >= n)
p = pollard_rho(p, c--);//不断找因子，知道找到为止，返回n说明没找到
Find(p, c);
Find(n / p, c);
}
int main()
{
ll n;srand((unsigned)time(NULL));
while(cin >> n)
{
m.clear();
Find(n, rand() % (n - 1) + 1);//这是自己设置的一个数
cout<<n<<" = ";
for(map<ll ,int>::iterator it = m.begin(); it != m.end();)
{
cout<<it->first<<" ^ "<<it->second;
if((++it) != m.end())
cout<<" * ";
}
cout<<endl;
}
return 0;
}
欧拉筛
int pre[1000000+10];
int vis[1000000+10];
vector<int>isp;
void eur()
{
for(auto i=2;i<1e6+10;++i){
if(!vis[i]){
isp.push_back(i);
pre[i]=i;
}
for(auto j:isp){
if(i*j>=1e6+10) break;
vis[i*j]=1;
pre[i*j]=j;
if(i%j==0) break;
}
}
}
void init() {
phi[1] = 1;
for (int i = 2; i < MAXN; ++i) {
if (!vis[i]) {
phi[i] = i - 1;
pri[cnt++] = i;
}
for (int j = 0; j < cnt; ++j) {
if (1ll * i * pri[j] >= MAXN) break;
vis[i * pri[j]] = 1;
if (i % pri[j]) {
phi[i * pri[j]] = phi[i] * (pri[j] - 1);
} else {
// i % pri[j] == 0
// 换言之，i 之前被 pri[j] 筛过了
// 由于 pri 里面质数是从小到大的，所以 i 乘上其他的质数的结果一定也是
// pri[j] 的倍数 它们都被筛过了，就不需要再筛了，所以这里直接 break
// 掉就好了
phi[i * pri[j]] = phi[i] * pri[j];
break;
}
}
}
}
线性代数
高斯消元
- 整型
int a[N][N];//增广矩阵
int x[N];//解集
bool freeX[N];//标记是否为自由变元
int GCD(int a,int b){
return !b?a:GCD(b,a%b);
}
int LCM(int a,int b){
return a/GCD(a,b)*b;
}
int Gauss(int equ,int var){//返回自由变元个数
/*初始化*/
for(int i=0;i<=var;i++){
x[i]=0;
freeX[i]=true;
}
/*转换为阶梯阵*/
int col=0;//当前处理的列
int row;//当前处理的行
for(row=0;row<equ&&col<var;row++,col++){//枚举当前处理的行
int maxRow=row;//当前列绝对值最大的行
for(int i=row+1;i<equ;i++){//寻找当前列绝对值最大的行
if(abs(a[i][col])>abs(a[maxRow][col]))
maxRow=i;
}
if(maxRow!=row){//与第row行交换
for(int j=row;j<var+1;j++)
swap(a[row][j],a[maxRow][j]);
}
if(a[row][col]==0){//col列第row行以下全是0，处理当前行的下一列
row--;
continue;
}
for(int i=row+1;i<equ;i++){//枚举要删去的行
if(a[i][col]!=0){
int lcm=LCM(abs(a[i][col]),abs(a[row][col]));
int ta=lcm/abs(a[i][col]);
int tb=lcm/abs(a[row][col]);
if(a[i][col]*a[row][col]<0)//异号情况相加
tb=-tb;
for(int j=col;j<var+1;j++) {
a[i][j]=a[i][j]*ta-a[row][j]*tb;
}
}
}
}
/*求解*/
//无解：化简的增广阵中存在(0,0,...,a)这样的行，且a!=0
for(int i=row;i<equ;i++)
if (a[i][col]!=0)
return -1;
//无穷解: 在var*(var+1)的增广阵中出现(0,0,...,0)这样的行
int temp=var-row;//自由变元有var-row个
if(row<var)//返回自由变元数
return temp;
//唯一解: 在var*(var+1)的增广阵中形成严格的上三角阵
for(int i=var-1;i>=0;i--){//计算解集
int temp=a[i][var];
for(int j=i+1;j<var;j++){
if(a[i][j]!=0)
temp-=a[i][j]*x[j];
}
if(temp%a[i][i]!=0)//有浮点数解，无整数解
return -2;
x[i]=temp/a[i][i];
}
return 0;
}
int main(){
int equ,var;//equ个方程，var个变元
while(scanf("%d%d",&equ,&var)!=EOF) {
memset(a,0,sizeof(a));
for(int i=0;i<equ;i++)//输入增广矩阵
for(int j=0;j<var+1;j++)
scanf("%d",&a[i][j]);
int freeNum=Gauss(equ,var);//自由元个数
if(freeNum==-1)//无解
printf("无解
");
else if(freeNum==-2)//有浮点数解无整数解
printf("无整数解
");
else if(freeNum>0){//有无穷多解
printf("有无穷多解，自由变元个数为%d
",freeNum);
for(int i=0;i<var;i++){
if(freeX[i])
printf("x%d是自由变元
",i+1);
else
printf("x%d=%d
",i+1,x[i]);
}
}
else{//有唯一解
for(int i=0;i<var;i++)
printf("x%d=%d
",i+1,x[i]);
}
printf("
");
}
return 0;
}
- 浮点
double a[N][N];//增广矩阵
double x[N];//解集
bool freeX[N];//标记是否为自由变元
int Gauss(int equ,int var){//返回自由变元个数
/*初始化*/
for(int i=0;i<=var;i++){
x[i]=0;
freeX[i]=true;
}
/*转换为阶梯阵*/
int col=0;//当前处理的列
int row;//当前处理的行
for(row=0;row<equ&&col<var;row++,col++){//枚举当前处理的行
int maxRow=row;//当前列绝对值最大的行
for(int i=row+1;i<equ;i++){//寻找当前列绝对值最大的行
if(abs(a[i][col])>abs(a[maxRow][col]))
maxRow=i;
}
if(maxRow!=row){//与第row行交换
for(int j=row;j<var+1;j++)
swap(a[row][j],a[maxRow][j]);
}
if(fabs(a[row][col])<1e6){//col列第row行以下全是0，处理当前行的下一列
row--;
continue;
}
for(int i=row+1;i<equ;i++){//枚举要删去的行
if(fabs(a[i][col])>1e6){
double temp=a[i][col]/a[row][col];
for(int j=col;j<var+1;j++)
a[i][j]-=a[row][j]*temp;
a[i][col]=0;
}
}
}
/*求解*/
//无解
for(int i=row;i<equ;i++)
if(fabs(a[i][col])>1e6)
return -1;
//无穷解: 在var*(var+1)的增广阵中出现(0,0,...,0)这样的行
int temp=var-row;//自由变元有var-row个
if(row<var)//返回自由变元数
return temp;
//唯一解: 在var*(var+1)的增广阵中形成严格的上三角阵
for(int i=var-1;i>=0;i--){//计算解集
double temp=a[i][var];
for(int j=i+1;j<var;j++)
temp-=a[i][j]*x[j];
x[i]=temp/a[i][i];
}
return 0;
}
- 模线性
int a[N][N];//增广矩阵
int x[N];//解集
bool freeX[N];//标记是否为自由变元
int GCD(int a,int b){
return !b?a:GCD(b,a%b);
}
int LCM(int a,int b){
return a/GCD(a,b)*b;
}
int Gauss(int equ,int var){//返回自由变元个数
/*初始化*/
for(int i=0;i<=var;i++){
x[i]=0;
freeX[i]=true;
}
/*转换为阶梯阵*/
int col=0;//当前处理的列
int row;//当前处理的行
for(row=0;row<equ&&col<var;row++,col++){//枚举当前处理的行
int maxRow=row;//当前列绝对值最大的行
for(int i=row+1;i<equ;i++){//寻找当前列绝对值最大的行
if(abs(a[i][col])>abs(a[maxRow][col]))
maxRow=i;
}
if(maxRow!=row){//与第row行交换
for(int j=row;j<var+1;j++)
swap(a[row][j],a[maxRow][j]);
}
if(a[row][col]==0){//col列第row行以下全是0，处理当前行的下一列
row--;
continue;
}
for(int i=row+1;i<equ;i++){//枚举要删去的行
if(a[i][col]!=0){
int lcm=LCM(abs(a[i][col]),abs(a[row][col]));
int ta=lcm/abs(a[i][col]);
int tb=lcm/abs(a[row][col]);
if(a[i][col]*a[row][col]<0)//异号情况相加
tb=-tb;
for(int j=col;j<var+1;j++) {
a[i][j]=((a[i][j]*ta-a[row][j]*tb)%MOD+MOD)%MOD;
}
}
}
}
/*求解*/
//无解：化简的增广阵中存在(0,0,...,a)这样的行，且a!=0
for(int i=row;i<equ;i++)
if (a[i][col]!=0)
return -1;
//无穷解: 在var*(var+1)的增广阵中出现(0,0,...,0)这样的行
int temp=var-row;//自由变元有var-row个
if(row<var)//返回自由变元数
return temp;
//唯一解: 在var*(var+1)的增广阵中形成严格的上三角阵
for(int i=var-1;i>=0;i--){//计算解集
int temp=a[i][var];
for(int j=i+1;j<var;j++){
if(a[i][j]!=0)
temp-=a[i][j]*x[j];
temp=(temp%MOD+MOD)%MOD;//取模
}
while(temp%a[i][i]!=0)//外层每次循环都是求a[i][i]，它是每个方程中唯一一个未知的变量
temp+=MOD;//a[i][i]必须为整数，加上周期MOD
x[i]=(temp/a[i][i])%MOD;//取模
}
return 0;
}
-
异或方程组
-
[][ ]
int a[N][N];//增广矩阵
int x[N];//解集
int freeX[N];//自由变元
int Gauss(int equ,int var){//返回自由变元个数
/初始化/
for(int i=0;i<=var;i++){
x[i]=0;
freeX[i]=0;
}
/*转换为阶梯阵*/
int col=0;//当前处理的列
int num=0;//自由变元的序号
int row;//当前处理的行
for(row=0;row<equ&&col<var;row++,col++){//枚举当前处理的行
int maxRow=row;//当前列绝对值最大的行
for(int i=row+1;i<equ;i++){//寻找当前列绝对值最大的行
if(abs(a[i][col])>abs(a[maxRow][col]))
maxRow=i;
}
if(maxRow!=row){//与第row行交换
for(int j=row;j<var+1;j++)
swap(a[row][j],a[maxRow][j]);
}
if(a[row][col]==0){//col列第row行以下全是0，处理当前行的下一列
freeX[num++]=col;//记录自由变元
row--;
continue;
}
for(int i=row+1;i<equ;i++){
if(a[i][col]!=0){
for(int j=col;j<var+1;j++){//对于下面出现该列中有1的行，需要把1消掉
a[i][j]^=a[row][j];
}
}
}
}
/*求解*/
//无解：化简的增广阵中存在(0,0,...,a)这样的行，且a!=0
for(int i=row;i<equ;i++)
if(a[i][col]!=0)
return -1;
//无穷解: 在var*(var+1)的增广阵中出现(0,0,...,0)这样的行
int temp=var-row;//自由变元有var-row个
if(row<var)//返回自由变元数
return temp;
//唯一解: 在var*(var+1)的增广阵中形成严格的上三角阵
for(int i=var-1;i>=0;i--){//计算解集
x[i]=a[i][var];
for(int j=i+1;j<var;j++)
x[i]^=(a[i][j]&&x[j]);
}
return 0;
}
int enumFreeX(int freeNum,int var){//枚举自由元，统计有解情况下1最少的个数
int sta=(1<<(freeNum));//自由元的状态总数
int res=INF;
for(int i=0;i<sta;++i){//枚举状态
int cnt=0;
for(int j=0;j<freeNum;j++){//枚举自由元
if(i&(1<<j)){
cnt++;
x[freeX[j]]=1;
}else
x[freeX[j]]=0;
}
for(int k=var-freeNum-1;k>=0;k--){//没有自由元的最下面一行
int index=0;
for(index=k;k<var;index++){//在当前行找到第一个非0自由元
if(a[k][index])
break;
}
x[index]=a[k][var];
for(int j=index+1;j<var;++j){//向后依次计算出结果
if(a[k][j])
x[index]^=x[j];
}
cnt+=x[index];//若结果为1，则进行统计
}
res=min(res,cnt);
}
return res;
}
int main(){
memset(a,0,sizeof(a));
int equ,var;
scanf("%d%d",&equ,&var);
for(int i=0;i<equ;i++){//构造初始状态
}
for(int i=0;i<equ;i++)//最终状态
scanf("%d",&a[i][var]);
int freeNum=Gauss(equ,var);//获取自由元
if(freeNum==-1)//无解
printf("inf
");
else if(freeNum==0){//唯一解
int res=0;
for(int i=0;i<var;i++)
res+=x[i];
printf("%d
",res);
}
else{//多个解
int res=enumFreeX(freeNum,var);
printf("%d
",res);
}
return 0;
}