高精度加法
for(i=0; i<len+1; i++)
{
ans[i]=(num1[i]+num2[i]+x)%10;
x=(num1[i]+num2[i]+x)/10;
}
for(i=len; !ans[i] && i>=0; i--);
if(i==-1) printf("0");
else
for(; i>=0; i--)
printf("%d", ans[i]);
高精度乘法
for(i=0; i<len1; i++)
for(j=0; j<len2; j++)
ans[i+j]+=num1[i]*num2[j];
for(i=0; i<len1+len2; i++)
if(ans[i]>9)
{
ans[i+1]+=ans[i]/10;
ans[i]%=10;
}
for(; !ans[i] && i>=0; i--);
if(i==-1) printf("0");
else
for(; i>=0; i--)
printf("%d", ans[i]);
快速乘法
long long Q_multiply(long long a, long long b) {
long long res = 0;
while(b) {
if(b & 1) {
res = (res + a) % p;
}
b >>= 1;
a = (a + a) % p;
}
return res;
}
二分匹配
bool _find(int x)
{
int i,j;
for(j=m+1;j<=n;j++)
{
if(line[x][j]==1 && used[j]==0)
{
used[j]=1;
if(fore[j]==0 || _find(fore[j]))
{
fore[j]=x;
return true;
}
}
}
return false;
}
//main函数
for(int i=1;i<=m;i++)
{
memset(used,0,sizeof(used));
if(_find(i)) all+=1;
}
阶乘长度（Stirling公式）
res=(log10(2*pi*N)*0.5+N*log10(N/e))+1;
并查集
void make_set(int n)
{
for(int i=0;i<=n;i++) pre[i]=i;
}
int Find_set(int x)
{
return x==pre[x]?x:pre[x]=Find_set(pre[x]);
}
bool Union(int x,int y)
{
int GrandX=Find_set(x);
int GrandY=Find_set(y);
if(GrandX==GrandY) return false;
else
{
pre[max(GrandX,GrandY)]=min(GrandX,GrandY);
return true;
}
}
//main函数
for(int i=0;i<n*(n-1)/2;i++)
{
if(Union(node[i].u,node[i].v))
{
ans+=node[i].c;
}
}
树状数组
int lowbit(int k)
{
return k&(-k);
}
void add(int i,int x)
{
while(i<=n)
{
tree[i]+=x;
i+=lowbit(i);
}
}
int get_sum(int k)
{
int ans=0;
while(k)
{
ans+=tree[k];
k-=lowbit(k);
}
return ans;
}
树状数组的逆序数
for(int i=1;i<=n;i++)
{
add(b[i],1);
sum+=getsum(n)-getsum(b[i]);
}
凸包板子
//hdu 1348
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1006;
const double pi = acos(-1.0);
struct node{
double x,y;
}p[maxn],P[maxn];
int n,tot;
double ans,l;
double X(node a,node b,node c){
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
double len(node a,node b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool cmp(node a,node b){
double pp = X(p[0],a,b);
if(pp>0) return true;
if(pp<0) return false;
return len(p[0],a)<len(p[0],b);
}
int main()
{
int t;
scanf("%d",&t);
for(int cas=1;cas<=t;cas++){
if(cas!=1) printf("\n");
scanf("%d%lf",&n,&l);
ans=2*pi*l;
for(int i=0;i<n;i++){
scanf("%lf%lf",&p[i].x,&p[i].y);
}
if(n==1) printf("%.0f\n",ans);
else if(n==2) printf("%.0f\n",ans+len(p[0],p[1]));
else{
for(int i=0;i<n;i++){
if(p[i].y<p[0].y){
/*
node tmp;
tmp.x=p[i].x; tmp.y=p[i].y;
p[i].x=p[0].x; p[i].y=p[0].y;
p[0].x=tmp.x; p[0].y=tmp.y;
*/
swap(p[i],p[0]);
}else if(p[i].y==p[0].y&&p[i].x<p[0].x){
/*
node tmp;
tmp.x=p[i].x; tmp.y=p[i].y;
p[i].x=p[0].x; p[i].y=p[0].y;
p[0].x=tmp.x; p[0].y=tmp.y;
*/
swap(p[i],p[0]);
}
}
sort(p+1,p+n,cmp);
P[0]=p[0];
P[1]=p[1];
tot=1;
for(int i=2;i<n;i++){
while(tot>0&&X(P[tot-1],P[tot],p[i])<=0) tot--;
tot++;
P[tot]=p[i];
}
for(int i=0;i<tot;i++){
ans+=len(P[i],P[i+1]);
}
ans+=len(P[0],P[tot]);
printf("%.0f\n",ans);
}
}
}
线段树板子
/********************************
Author: Audrey_H
Motto:talk is cheap,show me the code.
********************************/
//#include<bits/stdc++.h>
#include<stdio.h>
#include<string.h>
#include<string>
#include<math.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<stdlib.h>
#define lowbit(x) (x&(-x))
#define ll long long
#define PI acos(-1)
#define FILEIN freopen("in.txt","r",stdin)
#define FILEOUT freopen("out.txt","w",stdout)
#define CLR(x) memset(x,0,sizeof(x))
#define MEM(a,x) memset(a,x,sizeof(a))
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fll;
using namespace std;
//const double eps = 1e-6;
const ll mod = 1e9+7;
const int maxn = 500100;
const int maxe = 1e6+100;
using namespace std;
int n;
struct node{
int l,r;
ll sum,add;
}tree[4*maxn];
int a[maxn];
void Pushup(int rt){
tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
}
void Pushdown(int rt){
if(tree[rt].add){
tree[rt<<1].add+=tree[rt].add;
tree[rt<<1].sum+=(tree[rt<<1].r-tree[rt<<1].l+1)*tree[rt].add;
tree[rt<<1|1].add+=tree[rt].add;
tree[rt<<1|1].sum+=(tree[rt<<1|1].r-tree[rt<<1|1].l+1)*tree[rt].add;
tree[rt].add=0;
}
}
void Creat(int rt,int l,int r){
tree[rt].l=l;
tree[rt].r=r;
tree[rt].add=0;
if(l==r){
tree[rt].sum=a[l];
return ;
}
int mid=(l+r)>>1;
Creat(rt<<1,l,mid);
Creat(rt<<1|1,mid+1,r);
Pushup(rt);
}
void Updata(int rt,int u,int v,int add){
if(tree[rt].l>=u && tree[rt].r<=v){
tree[rt].add+=add;
tree[rt].sum+=(tree[rt].r-tree[rt].l+1)*add;
return ;
}
Pushdown(rt);
if(tree[rt<<1].r>=u){
Updata(rt<<1,u,v,add);
}
if(tree[rt<<1|1].l<=v){
Updata(rt<<1|1,u,v,add);
}
Pushup(rt);
}
ll Query(int rt,int u,int v)
{
if(tree[rt].l==u&&tree[rt].r==v){
return tree[rt].sum;
}
Pushdown(rt);
if(tree[rt<<1|1].l<=u){
return Query(rt<<1|1,u,v);
}else if(tree[rt<<1].r>=v){
return Query(rt<<1,u,v);
}else{
return Query(rt<<1|1,tree[rt<<1|1].l,v)+Query(rt<<1,u,tree[rt<<1].r);
}
}
int main()
{
//FILEIN
//FILEOUT
//std::ios::sync_with_stdio(false);
int n,m;
ll add;
char str[5];
while(scanf("%d%d",&n,&m)!=EOF){
memset(tree,0,sizeof(tree));
memset(a,0,sizeof(a));
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
Creat(1,1,n);
while(m--){
ll ans=0;
scanf("%s",str);
if(str[0]=='C'){
int l,r;
scanf("%d%d%lld",&l,&r,&add);
Updata(1,l,r,add);
}else{
int l,r;
scanf("%d%d",&l,&r);
printf("%lld\n",Query(1,l,r));
}
}
}
return 0;
}
这才是正宗的矩阵！
struct matrix{
ll mat[80][80];
ll *operator[](int x){
return mat[x];
}
matrix(){
CLR(mat);
}
matrix operator*(matrix &b){
matrix c;
for(int i = 1;i <= n + n;i++){
for(int j = 1;j <= n + n;j++){
for(int k = 1;k <= n + n;k++){
c[i][j] += mat[i][k] * b[k][j];
c[i][j] %= m; //如果有求模需求
}
}
}
return c;
}
};
网友评论