sweet

sweet
10个月前
#include<bits/stdc++.h>
using namespace std;
int n,a[100005];
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+n+1);
int ans=0;
for(int i=1;i<=n;i++)ans+=abs(a[i]-a[(n+1)/2]);
cout<<ans;
return 0;
}


sweet
10个月前
// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.
class Solution {
public:
vector<int> specialSort(int N) {
vector<int> res;
res.push_back(1);
for(int i=2;i<=N;i++){
int l=0,r=res.size()-1;
while(l<=r){
int mid=l+r>>1;
if(compare(res[mid],i))l=mid+1;
else r=mid-1;
}
res.push_back(i);
for(int j=res.size()-2;j>r;j--)swap(res[j],res[j+1]);
}
return res;
}
};


sweet
11个月前
#include<bits/stdc++.h>
using namespace std;
double n,cow[100005],m;
double sum[100005];
int check(double x){
for(int i=1;i<=n;i++)sum[i]=sum[i-1]+cow[i]-x;
double minv=0;
for(int i=m,j=0;i<=n;i++,j++){
minv=min(minv,sum[j]);
if(sum[i]>=minv)return 1;
}
return 0;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>cow[i];
double l=0,r=2000;
while(r-l>1e-5){
double mid=(l+r)/2;
if(check(mid))l=mid;
else r=mid;
}
cout<<int(r*1000);
return 0;
}


sweet
2019-05-27 13:04
#include <bits/stdc++.h>
using namespace std;
#define ll long long
pair<ll,ll> a[10100];
map<ll,ll> q;
ll n,m,i,j,k,p,h,c[10100],d[10100];
int main()
{
cin>>n>>p>>h>>m;
for(i=1;i<=m;i++){
ll A,B;
cin>>A>>B;
if(A>B)swap(A,B);
if(q[A]!=B)a[i]=make_pair(A,B),q[A]=B,d[A+1]--,d[B]++;
}
for(i=1;i<=n;i++)c[i]=c[i-1]+d[i];
for(i=1;i<=n;i++)cout<<c[i]+h<<endl;
return 0;
}


sweet
2019-02-10 09:59
#include<bits/stdc++.h>
using namespace std;
priority_queue<int>q;
int main()
{
int n,i,x,a=0,t;
cin>>n;
for(i=0;i<n;i++){
cin>>x;
q.push(-x);
}
for(i=1;i<n;i++){
t=q.top();
a-=q.top();
q.pop();
t+=q.top();
a-=q.top();
q.pop();
q.push(t);
}
cout<<a;
return 0;
}


sweet
2019-02-10 09:56
class MinStack {
public:
stack<int> SV,SM;
/** initialize your data structure here. */
MinStack() {

}

void push(int x) {
SV.push(x);
if(SM.empty()||x<SM.top())SM.push(x);
}

void pop() {
if(SV.top()==SM.top())SM.pop();
SV.pop();
}

int top() {
return SV.top();
}

int getMin() {
return SM.top();
}
};

/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/


sweet
2019-02-09 03:45
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n,a[100005];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=n;i>=1;i--)a[i]=a[i]-a[i-1];
LL pos=0,neg=0;
for(int i=2;i<=n;i++)
if(a[i]>0)pos+=a[i];
else neg-=a[i];
cout<<max(neg,pos)<<endl<<abs(pos-neg)+1;
return 0;
}


sweet
2019-02-09 03:45
#include<bits/stdc++.h>
using namespace std;
int x,y,w,N,R,n,m,g[5005][5005],ans=-1;
int main()
{
cin>>N>>R;
n=R,m=R;
while(N--){
cin>>x>>y>>w;
x++,y++;
g[x][y]=w;
n=max(n,x);
m=max(m,y);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
g[i][j]+=g[i-1][j]+g[i][j-1]-g[i-1][j-1];
for(int i=R;i<=n;i++)
for(int j=R;j<=m;j++)
ans=max(ans,g[i][j]-g[i-R][j]-g[i][j-R]+g[i-R][j-R]);
cout<<ans;
return 0;
}


sweet
2019-02-09 03:06

### 题目描述

#### 样例

样例输入：
3 4

7


#### 算法一

BFS大法闪亮登场！

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <deque>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

int n,m,t;
vector<int> f;
vector<int> e;
vector<int> u;
vector<int> pre;
vector<int> vis;
vector<vector<int> > c;
vector<vector<int> > p;
vector<vector<int> > ce;
vector<vector<int> > cw;
deque<int> q;

void add_edge_1(int x,int y,int c_v,int p_v)
{
cw[x].push_back(y);
c[x].push_back(c_v);
p[x].push_back(p_v);
ce[y].push_back(cw[x].size()-1);
cw[y].push_back(x);
c[y].push_back(0);
p[y].push_back(-p_v);
ce[x].push_back(cw[y].size()-1);
}

int bfs_1(int s,int t,int *flow,int *cost)
{
f.resize(0);
f.resize(cw.size(),0);
f[s]=oo_max;
e.resize(0);
e.resize(cw.size(),-1);
u.resize(0);
u.resize(cw.size(),oo_max);
u[s]=0;
pre.resize(0);
pre.resize(cw.size(),-1);
pre[s]=s;
vis.resize(0);
vis.resize(cw.size(),0);
for (q.resize(0),vis[s]=1,q.push_back(s);(!q.empty());vis[q.front()]=0,q.pop_front())
{
int now=q.front();
for (int i=0;i<cw[now].size();i++)
if (c[now][i]&&u[now]+p[now][i]<u[cw[now][i]])
{
f[cw[now][i]]=min(c[now][i],f[now]);
e[cw[now][i]]=i;
u[cw[now][i]]=u[now]+p[now][i];
pre[cw[now][i]]=now;
if (vis[cw[now][i]]==0)
vis[cw[now][i]]=1,q.push_back(cw[now][i]);
}
}
(*flow)=f[t];
(*cost)=u[t];
return (pre[t]!=-1);
}

void min_cost_max_flow_1(int s,int t,int *flow,int *cost)
{
int temp_flow,temp_cost;
while (bfs_1(s,t,&temp_flow,&temp_cost))
{
for (int i=t;i!=s;i=pre[i])
c[pre[i]][e[i]]-=temp_flow,c[i][ce[pre[i]][e[i]]]+=temp_flow;
(*flow)+=temp_flow;
(*cost)+=temp_cost;
}
}

int a,b;

int main()
{
scanf("%d%d",&a,&b);
cw.resize(0);
cw.resize(2);
ce.resize(0);
ce.resize(cw.size());
c.resize(0);
c.resize(cw.size());
p.resize(0);
p.resize(cw.size());
add_edge_1(0,1,oo_max,a);
add_edge_1(0,1,oo_max,b);
int ans_flow=0,ans_cost=0;
min_cost_max_flow_1(0,1,&ans_flow,&ans_cost);
printf("%d\n",ans_cost);
}


### 算法二

Dijkstra求最短路

#include<bits/stdc++.h>
using namespace std;
const int N=405;
struct Edge {
int v,w;
};
vector<Edge> edge[N*N];
int n;
int dis[N*N];
bool vis[N*N];
struct cmp {
bool operator()(int a,int b) {
return dis[a]>dis[b];
}
};
int Dijkstra(int start,int end)
{
priority_queue<int,vector<int>,cmp> dijQue;
memset(dis,-1,sizeof(dis));
memset(vis,0,sizeof(vis));
dijQue.push(start);
dis[start]=0;
while(!dijQue.empty()) {
int u=dijQue.top();
dijQue.pop();
vis[u]=0;
if(u==end)
break;
for(int i=0;i<edge[u].size();i++) {
int v=edge[u][i].v;
if(dis[v]==-1||dis[v]>dis[u]+edge[u][i].w) {
dis[v]=dis[u]+edge[u][i].w;
if(!vis[v]) {
vis[v]=true;
dijQue.push(v);
}
}
}
}
return dis[end];
}
int main()
{
int a,b;
scanf("%d%d",&a,&b);
Edge Qpush;
Qpush.v=1;
Qpush.w=a;
edge[0].push_back(Qpush);
Qpush.v=2;
Qpush.w=b;
edge[1].push_back(Qpush);
printf("%d",Dijkstra(0,2));
return 0;
}


#### 算法三

Floyd算法

#include<bits/stdc++.h>
using namespace std;
long long n=3,a,b,dis[4][4];
int main()
{
cin>>a>>b;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dis[i][j]=2147483647;
dis[1][2]=a,dis[2][3]=b;
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
cout<<dis[1][3];
return 0;
}


#### 算法四

LCT

#include<bits/stdc++.h>
using namespace std;
struct node
{
int data,rev,sum;
node *son[2],*pre;
bool judge();
bool isroot();
void pushdown();
void update();
void setson(node *child,int lr);
}lct[233];
int top,a,b;
node *getnew(int x)
{
node *now=lct+ ++top;
now->data=x;
now->pre=now->son[1]=now->son[0]=lct;
now->sum=0;
now->rev=0;
return now;
}
bool node::judge()
{
return pre->son[1]==this;
}
bool node::isroot()
{
if(pre==lct)return true;
return !(pre->son[1]==this||pre->son[0]==this);
}
void node::pushdown()
{
if(this==lct||!rev)return;
swap(son[0],son[1]);
son[0]->rev^=1;
son[1]->rev^=1;
rev=0;
}
void node::update()
{
sum=son[1]->sum+son[0]->sum+data;
}
void node::setson(node *child,int lr)
{
this->pushdown();
child->pre=this;
son[lr]=child;
this->update();
}
void rotate(node *now)
{
node *father=now->pre,*grandfa=father->pre;
if(!father->isroot()) grandfa->pushdown();
father->pushdown();
now->pushdown();
int lr=now->judge();
father->setson(now->son[lr^1],lr);
if(father->isroot()) now->pre=grandfa;
else grandfa->setson(now,father->judge());
now->setson(father,lr^1);
father->update();
now->update();
if(grandfa!=lct) grandfa->update();
}
void splay(node *now)
{
if(now->isroot())return;
for(; !now->isroot(); rotate(now))
if(!now->pre->isroot())
now->judge()==now->pre->judge()?rotate(now->pre):rotate(now);
}
node *access(node *now)
{
node *last=lct;
for(; now!=lct; last=now,now=now->pre) {
splay(now);
now->setson(last,1);
}
return last;
}
void changeroot(node *now)
{
access(now)->rev^=1;
splay(now);
}
void connect(node *x,node *y)
{
changeroot(x);
x->pre=y;
access(x);
}
void cut(node *x,node *y)
{
changeroot(x);
access(y);
splay(x);
x->pushdown();
x->son[1]=y->pre=lct;
x->update();
}
int query(node *x,node *y)
{
changeroot(x);
node *now=access(y);
return now->sum;
}
int main()
{
scanf("%d%d",&a,&b);
node *A=getnew(a);
node *B=getnew(b);
connect(A,B);
cut(A,B);
connect(A,B);
printf("%d",query(A,B));
return 0;
}


#### 算法五

main自递归和位运算

#include<bits/stdc++.h>
int main(int a,int b,int k)
{
if(k)scanf("%d%d",&a,&b);
printf("%d",b==0?a:main(a^b,(a&b)<<1,0));
exit(0);
}


#### 算法六

SPFA

#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,op,l,r,u,v1,e;
int head[200009],ne_xt[200009],dis[200009];
int len[200009],v[200009],team[200009],pd[100009];
int lt(int x,int y,int z)
{
op++;
v[op]=y;
ne_xt[op]=head[x];
head[x]=op;
len[op]=z;
}
int SPFA(int s,int f)
{
for(int i=1;i<=200009;i++){dis[i]=999999999;}
l=0,r=1,team[1]=s,pd[s]=1,dis[s]=0;
while(l!=r){
l=(l+1)%90000,u=team[l],pd[u]=0,e=head[u];
while(e!=0){
v1=v[e];
if(dis[v1]>dis[u]+len[e]){
dis[v1]=dis[u]+len[e];
if(!pd[v1]){
r=(r+1)%90000,
team[r]=v1,
pd[v1]=1;
}
}
e=ne_xt[e];
}
}
return dis[f];
}
int main()
{
scanf("%d%d",&a,&b);
lt(1,2,a);
lt(2,3,b);
printf("%d",SPFA(1,3));
return 0;
}


#### 算法七

#include<iostream>
using namespace std;
long long a,b,c;
long long dg(long long a)
{
if(a<=5)return a;
return (dg(a/2)+dg(a-a/2));
}
int main()
{
cin>>a>>b;
cout<<dg(a)+dg(b);
return 0;
}


#### 算法八

#include<iostream>
using namespace std;
long long a,b,c;
long long dg(long long a)
{
if(a<=5)return a;
return (dg(a/2)+dg(a-a/2));
}
int main()
{
cin>>a>>b;
cout<<dg(a)+dg(b);
return 0;
}


#### 算法九

#include<bits/stdc++.h>
using namespace std;
char a1[1000],b1[1000];
int a[1000],b[1000],c[1000],la,lb,lc=1,i,x;
int main()
{
cin>>a1>>b1;
la=strlen(a1);
lb=strlen(b1);
for(i=0;i<=la-1;i++)a[la-i]=a1[i]-'0';
for(i=0;i<=lb-1;i++)b[lb-i]=b1[i]-'0';
while(lc<=la||lc<=lb){c[lc]=a[lc]+b[lc]+x,x=c[lc]/10,c[lc]%=10,lc++;}
c[lc]=x;
if(c[lc]==0)lc--;
for(i=lc;i>=1;i--)cout<<c[i];
return 0;
}


#### 算法十

#include<bits/stdc++.h>
#define p 8
#define carry 100000000
using namespace std;
const int Maxn=50001;
char s1[Maxn],s2[Maxn];
int a[Maxn],b[Maxn],ans[Maxn];
int change(char s[],int n[])
{
char temp[Maxn];
int len=strlen(s+1),cur=0;
while(len/p){
strncpy(temp,s+len-p+1,p);
n[++cur]=atoi(temp);
len-=p;
}
if(len){
memset(temp,0,sizeof(temp));
strncpy(temp,s+1,len);
n[++cur]=atoi(temp);
}
return cur;
}
int add(int a[],int b[],int c[],int l1,int l2)
{
int x=0,l3=max(l1,l2);
for(int i=1;i<=l3;i++){
c[i]=a[i]+b[i]+x;
x=c[i]/carry;
c[i]%=carry;
}
while(x>0){c[++l3]=x%10;x/=10;}
return l3;
}
void print(int a[],int len)
{
printf("%d",a[len]);
for(int i=len-1;i>=1;i--)printf("%0*d",p,a[i]);
printf("\n");
}
int main()
{
scanf("%s%s",s1+1,s2+1);
int la=change(s1,a);
int lb=change(s2,b);
int len=add(a,b,ans,la,lb);
print(ans,len);
}


#### 算法十一

#include<bits/stdc++.h>
using namespace std;
#define set(x) Set(x)
#define REP(i,j,k) for (int i=(j),_end_=(k);i<=_end_;++i)
#define DREP(i,j,k) for (int i=(j),_start_=(k);i>=_start_;--i)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()-1))
#define ALL(x) ((x).begin()+1),(x).end()
template<typename T> inline bool chkmin(T &a,const T &b){ return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a,const T &b){ return a < b ? a = b, 1 : 0; }
typedef long long LL;
typedef pair<int,int> node;
const int dmax=1010,oo=0x3f3f3f3f;
int n,m;
int a[dmax][dmax] , ans;
int d[dmax],e[dmax];
priority_queue <node> q;
inline bool operator >(node a,node b){ return a.y>b.y; }
bool p[dmax];
void Set(int x){ p[x]=1; }
void unset(int x){ p[x]=0; }
bool check(int x){ return x!=1 && x!=n && !p[x] && e[x]>0; }
void preflow(){
e[1]=oo;
d[1]=n-1;
q.push(mp(1,n-1));
set(1);
while (!q.empty()){
bool flag=1;
int k=q.top().x;
q.pop(),unset(k);
DREP(i,n,1)
if ((d[k]==d[i]+1 || k==1) && a[k][i]>0){
flag=0;
int t=min(a[k][i],e[k]);
e[k]-=t;
a[k][i]-=t;
e[i]+=t;
a[i][k]+=t;
if (check(i)){
q.push(mp(i,d[i]));
set(i);
}
if (e[k]==0) break;
}
if (flag){
d[k]=oo;
REP(i,1,n)
if (a[k][i]>0)chkmin(d[k],d[i]+1);
}
if (check(k)){
q.push(mp(k,d[k]));
set(k);
}
}
ans=e[n];
}
int main(){
n = 2, m = 2;
int x, y;
scanf("%d%d", &x, &y);
a[1][2] += x + y;
preflow();
printf("%d\n",ans);
return 0;
}


#### 算法十二

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5000 + 10;
struct Tree
{
int l, r, val;
}t[MAXN * 4];
int N = 2, a[MAXN];
inline void init()
{
for(int i=1; i<=N; i++)
scanf("%d", &a[i]);
}
void Build(int Root, int L, int R)
{
t[Root].l = L;
t[Root].r = R;
t[Root].val = 0;
if(L == R) {
t[Root].val = a[L];
return ;
}
int m = (L + R) >> 1;
int Next = Root * 2;
Build(Next, L, m);
Build(Next+1, m+1, R);
t[Root].val = t[Next].val + t[Next+1].val;

}
void Updata(int Root, int pos, int _val)
{
if(t[Root].l == t[Root].r) {
t[Root].val += _val;
return ;
}
int Next = Root * 2;
int m = (t[Root].l + t[Root].r) >> 1;
if(pos <= m) Updata(Next, pos, _val);
else Updata(Next+1, pos, _val);
t[Root].val = t[Next].val + t[Next+1].val;
}
int Doit(int Root, int L, int R)
{
if(t[Root].l>=L && t[Root].r<=R)return t[Root].val;
int Ans = 0;
int Next = Root * 2;
int m=(t[Root].l + t[Root].r) >> 1;
if(L<=m)Ans+=Doit(Next,L,R);
if(R>m)Ans+=Doit(Next+1,L,R);
return Ans;
}
int main()
{
init();
Build(1,1,N);
int Ans=Doit(1,1,N);
printf("%d", Ans);
return 0;
}


#### 算法十三

#include <cstdio>
#include <algorithm>
#define INF 2140000000
using namespace std;
struct tree{int x,y,t;}a[10];
bool cmp(const tree&a,const tree&b)
{
return a.t<b.t;
}
int f[11],i,j,k,n,m,x,y,t,ans;
int root(int x)
{
if (f[x]==x) return x;
f[x]=root(f[x]);
return f[x];
}
int main()
{
for(i=1;i<=10;i++)f[i]=i;
for(i=1;i<=2;i++){
scanf("%d",&a[i].t);
a[i].x=i+1;a[i].y=1;k++;
}
a[++k].x=1;a[k].y=3,a[k].t=INF;
sort(a+1,a+1+k,cmp);
for(i=1;i<=k;i++){
x=root(a[i].x);
y=root(a[i].y);
if(x!=y)f[x]=y,ans+=a[i].t;
}
printf("%d",ans);
return 0;
}


# 好了，扯了那么多，我们来个正常的吧QWQ~~

#include<bits/stdc++.h>
using namespace std;
int a,b;
int main()
{
cin>>a>>b;
cout<<a+b<<endl;
return 0;
}


sweet
2019-02-08 12:31
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PLL;
LL T,N,A,B;
PLL calc(LL n,LL m)
{
if(n==0)return {0,0};
LL len=1ll<<(n-1),cnt=1ll<<(2*n-2);
auto pos=calc(n-1,m%cnt);
LL x=pos.first,y=pos.second;
LL z=m/cnt;
if(z==0)return {y,x};
else if(z==1)return {x,y+len};
else if(z==2)return {x+len,y+len};
return {2*len-1-y,len-1-x};
}
int main()
{
cin>>T;
while(T--){
cin>>N>>A>>B;
auto ac=calc(N,A-1);
auto bc=calc(N,B-1);
double x=abs(ac.first-bc.first),y=abs(ac.second-bc.second);
printf("%.0lf\n",sqrt(x*x+y*y)*10);
}
return 0
}