模版
wzb13958817049 · · 休闲·娱乐
快读
inline int read(){
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-48;ch=getchar();}
return x*f;
}区间加，区间查询
#include<bits/stdc++.h>
#define ll long long
inline ll read(){ll x = 0;bool f = 1;char ch = gc();while (ch > '9' || ch < '0') f = ch == '-' ? 0 : 1, ch = gc();while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();return f ? x : -x;}
using namespace std;
ll a[100005],n,m;
struct node{
ll sum,tag;
}tree[400005];
void build(int rt,int l,int r){
if(l==r){tree[rt].sum=a[l];return;}
int mid=l+r>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
}
void pushdown(int rt,int l,int r){
int mid=l+r>>1;
tree[rt<<1].tag+=tree[rt].tag;
tree[rt<<1].sum+=tree[rt].tag*(mid-l+1);
tree[rt<<1|1].tag+=tree[rt].tag;
tree[rt<<1|1].sum+=tree[rt].tag*(r-mid);
tree[rt].tag=0;
}
long long query(int rt,int l,int r,int x,int y){
if(x<=l && r<=y) return tree[rt].sum;
int mid=l+r>>1;
if(tree[rt].tag) pushdown(rt,l,r);
long long ret=0;
if(x<=mid) ret+=query(rt<<1,l,mid,x,y);
if(y>mid) ret+=query(rt<<1|1,mid+1,r,x,y);
return ret;
}
void modify(int rt,int l,int r,int x,int y,long long z){
if(x<=l && r<=y){tree[rt].tag+=z;tree[rt].sum+=(r-l+1)*z;return ;}
int mid=l+r>>1;
if(tree[rt].tag) pushdown(rt,l,r);
if(x<=mid) modify(rt<<1,l,mid,x,y,z);
if(y>mid) modify(rt<<1|1,mid+1,r,x,y,z);
tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
}
int main(){
ios::sync_with_stdio(0),cout.tie(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
build(1,1,n);
for(int i=1;i<=m;i++){
long long x,y,k,q;
cin>>q;
if(q==1){x=read();y=read();k=read();modify(1,1,n,x,y,k);}
else{x=read();y=read();printf("%lld\n",query(1,1,n,x,y));}
}
return 0;
}区间最大值
线段树
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e5+5;
long long a[N],n,m;
struct node{
long long sum,tag;
}tree[N];
void build(int rt,int l,int r){
if(l==r){tree[rt].sum=a[l];return;}
int mid=l+r>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
tree[rt].sum=max(tree[rt<<1].sum,tree[rt<<1|1].sum);
}
void pushdown(int rt,int l,int r){
int mid=l+r>>1;
tree[rt<<1].tag+=tree[rt].tag;
tree[rt<<1].sum+=tree[rt].tag;
tree[rt<<1|1].tag+=tree[rt].tag;
tree[rt<<1|1].sum+=tree[rt].tag;
tree[rt].tag=0;
}
long long query(int rt,int l,int r,int x,int y){
if(x<=l && r<=y) return tree[rt].sum;
int mid=l+r>>1;
if(tree[rt].tag) pushdown(rt,l,r);
long long ret=LLONG_MIN;
if(x<=mid) ret=max(ret,query(rt<<1,l,mid,x,y));
if(y>mid) ret=max(ret,query(rt<<1|1,mid+1,r,x,y));
return ret;
}
void modify(int rt,int l,int r,int x,int y,long long z){
if(x<=l && r<=y){tree[rt].tag+=z;tree[rt].sum+=z;return ;}
int mid=l+r>>1;
if(tree[rt].tag) pushdown(rt,l,r);
if(x<=mid) modify(rt<<1,l,mid,x,y,z);
if(y>mid) modify(rt<<1|1,mid+1,r,x,y,z);
tree[rt].sum=max(tree[rt<<1].sum,tree[rt<<1|1].sum);
}
int main(){
ios::sync_with_stdio(0),cout.tie(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
build(1,1,n);
for(int i=1;i<=m;i++){
long long x,y,k,q;
cin>>q;
if(q==1){cin>>x>>y>>k;modify(1,1,n,x,y,k);}
else{cin>>x>>y;cout<<query(1,1,n,x,y)<<"\n";}
}
return 0;
}高斯消元
约当消元法(整数解)
#include<bits/stdc++.h>
const double eps=1e-8;
#define ll long long
using namespace std;
ll n,m,x=1;
long double a[1005][505];
signed main(){
ios::sync_with_stdio(0),cout.tie(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++) for(int j=1;j<=n+1;j++) cin>>a[i][j];
for(int i=1;i<=n;i++){
int id=x;
for(int j=x;j<=m;j++) if(fabs(a[j][i])>fabs(a[id][i])) id=j;
if(fabs(a[id][i])>eps) swap(a[x],a[id]);
else{continue;}
for(int j=n+1;j>=i;--j) a[x][j]/=a[x][i];
for(int j=1;j<=m;j++){
if(j!=x){
for(int k=n+1;k>=i;--k) a[j][k]-=a[j][i]*a[x][k];
}
}
++x;
}
for(int i=x;i<=m;i++) if(fabs(a[i][n+1])>eps){cout<<"No solutions";return 0;}
if(x<=n){cout<<"Many solutions";return 0;}
for(int i=1;i<=n;i++) cout<<fixed<<setprecision(0)<<(ll)(a[i][n+1]+0.1)<<"\n";
return 0;
}实数解
约当
#include<bits/stdc++.h>
const double eps=1e-8;
#define ll long long
using namespace std;
ll n,m,x=1;
long double a[1005][505];
signed main(){
ios::sync_with_stdio(0),cout.tie(0),cin.tie(0);
cin>>n;
m=n;
for(int i=1;i<=m;i++) for(int j=1;j<=n+1;j++) cin>>a[i][j];
for(int i=1;i<=n;i++){
int id=x;
for(int j=x;j<=m;j++) if(fabs(a[j][i])>fabs(a[id][i])) id=j;
if(fabs(a[id][i])>eps) swap(a[x],a[id]);
else{continue;}
for(int j=n+1;j>=i;--j) a[x][j]/=a[x][i];
for(int j=1;j<=m;j++){
if(j!=x){
for(int k=n+1;k>=i;--k) a[j][k]-=a[j][i]*a[x][k];
}
}
++x;
}
for(int i=x;i<=m;i++) if(fabs(a[i][n+1])>eps){cout<<"No Solution";return 0;}
if(x<=n){cout<<"No Solution";return 0;}
for(int i=1;i<=n;i++) cout<<fixed<<setprecision(2)<<a[i][n+1]<<"\n";
return 0;
}普通高斯消元
#include<bits/stdc++.h>
const double eps=1e-8;
#define ll long long
using namespace std;
ll n;
double a[105][105],ans[105];
signed main(){
ios::sync_with_stdio(0),cout.tie(0),cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++) for(int j=1;j<=n+1;j++) cin>>a[i][j];
for(int i=1;i<=n;i++){
int x=i;
for(int j=i+1;j<=n;j++) if(fabs(a[j][i])>fabs(a[x][i])) x=j;
if(x!=i) for(int j=1;j<=n+1;j++) swap(a[x][j],a[i][j]);
if(fabs(a[i][i])<eps && fabs(a[i][n+1])<eps){cout<<"No Solution";return 0;}
bool falg=0;
for(int j=i;j<=n;j++) if(fabs(a[i][j])<eps){}else{falg=1;break;}
if(falg==0){cout<<"No Solution";return 0;}
for(int j=i+1;j<=n;j++){
double t=a[j][i]/a[i][i];
for(int k=i;k<=n+1;k++) a[j][k]-=t*a[i][k];
}
}
for(int i=n;i>=0;i--){
ans[i]=a[i][n+1]/a[i][i];
for(int j=i-1;j>0;j--) a[j][n+1]-=ans[i]*a[j][i];
}
for(int i=1;i<=n;i++) cout<<fixed<<setprecision(2)<<ans[i]<<"\n";
return 0;
}异或方程组
ll gauss(int n,int m){
int cnt=0,now=1;
for(int i=1;i<=n;i++){
int num=now;
for(int j=now;j<=m;j++){
if(a[j][i]){num=j;break;}
}
if(!a[num][i]) continue;
if(now!=num) swap(a[now],a[num]);
for(int j=1;j<=m;j++){
if(a[j][i]&&j!=now)
for(int k=1;k<=n+1;k++) a[j][k]^=a[now][k];
}
now++;
}
return n-now+1;
}造数据
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e5+5;
mt19937 rd(time(0));
string getname(string a,int i,string b){
stringstream ss;
ss<<a<<i<<b;
return ss.str();
}
ll n,a[N];
int main(){
ios::sync_with_stdio(0),cout.tie(0),cin.tie(0);
for(int i=1;i<=10;i++){
freopen(getname("Uxxxtest",i,".in").c_str(),"w",stdout);
n=rd();
cout<<n<<"\n";
for(int i=1;i<=n;i++){
a[i]=rd();
cout<<a[i]<<" ";
}
freopen(getname("Uxxxtest",i,".out").c_str(),"w",stdout);
for(int i=1;i<=n;i++) cout<<a[i]<<" ";
}
return 0;
}高精度
string add(string str1,string str2){string str;int len1=str1.length();int len2=str2.length();if(len1<len2){for(int i=1;i<=len2-len1;i++) str1="0"+str1;}else{for(int i=1;i<=len1-len2;i++) str2="0"+str2;}len1=str1.length();int cf=0;int temp;for(int i=len1-1;i>=0;i--){temp=str1[i]-'0'+str2[i]-'0'+cf;cf=temp/10;temp%=10;str=char(temp+'0')+str;}if(cf!=0) str=char(cf+'0')+str;return str;}
string mul(string str1,string str2){string str;int len1=str1.length();int len2=str2.length();string tempstr;for(int i=len2-1;i>=0;i--){tempstr="";int temp=str2[i]-'0';int t=0;int cf=0;if(temp!=0){for(int j=1;j<=len2-1-i;j++)tempstr+="0";for(int j=len1-1;j>=0;j--){t=(temp*(str1[j]-'0')+cf)%10;cf=(temp*(str1[j]-'0')+cf)/10;tempstr=char(t+'0')+tempstr;}if(cf!=0) tempstr=char(cf+'0')+tempstr;}str=add(str,tempstr);}str.erase(0,str.find_first_not_of('0'));return str;}
int sub(int *a,int *b,int La,int Lb){if(La<Lb) return -1;if(La==Lb){for(int i=La-1;i>=0;i--)if(a[i]>b[i]) break;else if(a[i]<b[i]) return -1;}for(int i=0;i<La;i++){ a[i]-=b[i]; if(a[i]<0) a[i]+=10,a[i+1]--; } for(int i=La-1;i>=0;i--) if(a[i]) return i+1;return 0;}
string div(string n1,string n2){string s,v;int a[L],b[L],r[L],La=n1.size(),Lb=n2.size(),i,tp=La;fill(a,a+L,0);fill(b,b+L,0);fill(r,r+L,0);for(i=La-1;i>=0;i--) a[La-1-i]=n1[i]-'0'; for(i=Lb-1;i>=0;i--) b[Lb-1-i]=n2[i]-'0'; if(La<Lb || (La==Lb && n1<n2)){return n1;} int t=La-Lb;for(int i=La-1;i>=0;i--)if(i>=t) b[i]=b[i-t]; else b[i]=0;Lb=La;for(int j=0;j<=t;j++){int temp;while((temp=sub(a,b+j,La,Lb-j))>=0){La=temp;r[t-j]++;} }for(i=0;i<L-10;i++) r[i+1]+=r[i]/10,r[i]%=10;while(!r[i]) i--;while(i>=0) s+=r[i--]+'0'; i=tp; while(!a[i]) i--;while(i>=0) v+=a[i--]+'0'; if(v.empty()) v="0"; return v; }