Lazy_tiger

ACM

6055

Lazy_tiger
7个月前
#include <bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <list>
#include <limits.h>
#define il inline
#define pf printf
#define sf(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define ll long long
#define ull unsigned long long
#define PII pair<int,int>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3fll
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
int dx[4]= {0,-1,0,1},dy[4]= {-1,0,1,0};
int dx8[8] = {0, 0, 1, -1, -1, -1, 1, 1}, dy8[8] = {1, -1, 0, 0, -1, 1, -1, 1};
int gcd(int a,int b)
{
return b? gcd(b,a%b) : a;
}
int lcm(int a,int b)
{
return a*b/gcd(a,b);
}
{
int x;
scanf("%d", &x);
return x;
}
const int N=2e6+10;
int a[N];
int main()
{
ios;
int n;cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
int mid=a[(n+1)/2];
ll sum=0;
for(int i=1;i<=n;i++) sum+=abs(a[i]-mid);
cout<<sum<<endl;
return 0;
}



Lazy_tiger
7个月前
#include <bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <list>
#include <limits.h>
#define il inline
#define pf printf
#define sf(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,e,s) for(int i=(e); i>=(s); --i)
#define ll long long
#define ull unsigned long long
#define PII pair<int,int>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3fll
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
int dx[4]= {0,-1,0,1},dy[4]= {-1,0,1,0};
int dx8[8] = {0, 0, 1, -1, -1, -1, 1, 1}, dy8[8] = {1, -1, 0, 0, -1, 1, -1, 1};
/*
int get_bitz(unsigned int x){return _builtin_ctz(x);}
int get_bitzll(unsigned int x){return _builtin_ctzll(x);}
int get_bitcount(unsigned int x){return _builtin_popcount(x);}
int get_bitcountll(unsigned int x){return _builtin_popcountll(x);}
*/
int gcd(int a,int b)
{
return b? gcd(b,a%b) : a;
}
int lcm(int a,int b)
{
return a*b/gcd(a,b);
}
{
int x;
scanf("%d", &x);
return x;
}
const int N=200020;
int n,m;
int ans,ans_n,ans_m,a[N];
map<int,int> mp;
int main()
{
ios;
scanf("%d",&n);
rep(i,1,n)
{
mp[x]++;
}
scanf("%d",&n);
rep(i,1,n) cin>>a[i];

rep(i,1,n)
{
if(mp[a[i]]>ans_n ||(mp[a[i]]==ans_n && mp[x]>ans_m))
ans=i,ans_n=mp[a[i]],ans_m=mp[x];
}
printf("%d \n",ans);
return 0;
}



Lazy_tiger
7个月前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <vector>
#define LL long long
#define INF 0x3f3f3f3f
#define PII pair<int,int>
#define PB push_back
#define POP pop_back()
#define FI first
#define SE second
#define ULL unsigned long long
using namespace std;
const double pi = acos(-1),eps=1e-8;
//const int maxn = 1 << 17;
const int N = 1000,NN = 1e7 + 1, M = 1 << 16, mod = 1e9 + 7;

class Solution{
public:
vector<int> specialSort(int N)
{
vector<int> res(1,1);
for(int i = 2; i <= N ; i ++)
{
int l = 0 , r = res.size() -1 ;
while(l < r)
{
int mid = (l + r + 1) >> 1;
if(compare(res[mid],i)) l = mid ;
else r =mid - 1;
}
res.push_back(i);
for(int j = res.size()-2;j > r; j --)
{
swap(res[j],res[j+1]);
}
if(compare(i,res[r])) swap(res[r],res[r+1]);
}
return res;
}
};



Lazy_tiger
7个月前

# define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

using namespace std;
int dx[4]= {0,-1,0,1},dy[4]= {-1,0,1,0};
int dx8[8] = {0, 0, 1, -1, -1, -1, 1, 1}, dy8[8] = {1, -1, 0, 0, -1, 1, -1, 1};
/
int get_bitz(unsigned int x){return _builtin_ctz(x);}
int get_bitzll(unsigned int x){return _builtin_ctzll(x);}
int get_bitcount(unsigned int x){return _builtin_popcount(x);}
int get_bitcountll(unsigned int x){return _builtin_popcountll(x);}
/
int gcd(int a,int b)
{
return b? gcd(b,a%b) : a;
}
int lcm(int a,int b)
{
return a*b/gcd(a,b);
}
const int N=2e6+10;
int n , F;
double a[N],s[N];
bool check(double x)
{
rep(i,1,n) s[i]=s[i-1]+a[i]-x;

double mins=0;
for(int k=F;k<=n;k++)
{
mins=min(mins,s[k-F]);
if(s[k]>mins)
return true;
}
return false;


}
int main()
{
ios;
cin>>n>>F;
double l=0,r=0;
rep(i,1,n)
{
cin>>a[i];
r=max(r,a[i]);
}
while(r-l>1e-5)
{
double mid=(l+r)/2;
if(check(mid)) l=mid;
else r=mid;
}
cout<<(int)(r*1000)<<endl;

return 0;


}



Lazy_tiger
8个月前
#include <bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <list>
#include <limits.h>
#define il inline
#define pf printf
#define sf(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,e,s) for(int i=(e); i>=(s); --i)
#define ll long long
#define ull unsigned long long
#define PII pair<int,int>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3fll
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
int dx[4]= {0,-1,0,1},dy[4]= {-1,0,1,0};
int dx8[8] = {0, 0, 1, -1, -1, -1, 1, 1}, dy8[8] = {1, -1, 0, 0, -1, 1, -1, 1};
/*
int get_bitz(unsigned int x){return _builtin_ctz(x);}
int get_bitzll(unsigned int x){return _builtin_ctzll(x);}
int get_bitcount(unsigned int x){return _builtin_popcount(x);}
int get_bitcountll(unsigned int x){return _builtin_popcountll(x);}
*/
int gcd(int a,int b)
{
return b? gcd(b,a%b) : a;
}
int lcm(int a,int b)
{
return a*b/gcd(a,b);
}
const int N=2e5+10,mod=9901;

struct node
{
int idx,x;
} nd[N];

int cmp(node a,node b)
{
return a.x<b.x;
}
int n,p,h,m;
int c[N],d[N];
map<PII,bool> existed;
int main()
{
ios;
cin>>n>>p>>h>>m;
for(int i=1;i<=m;i++)
{
int a,b;
cin>>a>>b;
if(a>b) swap(a,b);
if(existed[make_pair(a,b)]) continue;
d[a+1]--,d[b]++;
existed[make_pair(a,b)]=true;
}
for(int i=1;i<=n;i++)
{
c[i]=c[i-1]+d[i];
cout<<h+c[i]<<endl;
}
return 0;
}



Lazy_tiger
8个月前
#include <bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <list>
#include <limits.h>
#define il inline
#define pf printf
#define sf(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,e,s) for(int i=(e); i>=(s); --i)
#define ll long long
#define ull unsigned long long
#define PII pair<int,int>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3fll
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
int dx[4]= {0,-1,0,1},dy[4]= {-1,0,1,0};
int dx8[8] = {0, 0, 1, -1, -1, -1, 1, 1}, dy8[8] = {1, -1, 0, 0, -1, 1, -1, 1};
/*
int get_bitz(unsigned int x){return _builtin_ctz(x);}
int get_bitzll(unsigned int x){return _builtin_ctzll(x);}
int get_bitcount(unsigned int x){return _builtin_popcount(x);}
int get_bitcountll(unsigned int x){return _builtin_popcountll(x);}
*/
int gcd(int a,int b)
{
return b? gcd(b,a%b) : a;
}
int lcm(int a,int b)
{
return a*b/gcd(a,b);
}
const int N=2e5+10,mod=9901;

struct node
{
int idx,x;
} nd[N];

int cmp(node a,node b)
{
return a.x<b.x;
}
int n;
ll a[N];
int main()
{
ios;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
ll p=0,q=0;
for(int i=2;i<=n;i++)
{
ll t=a[i]-a[i-1];
if(t>0)
{
p+=t;
}
else
q-=t;
}
cout<<max(p,q)<<endl;
cout<<abs(p-q)+1<<endl;
return 0;
}



Lazy_tiger
8个月前
#include <bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <list>
#include <limits.h>
#define il inline
#define pf printf
#define sf(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,e,s) for(int i=(e); i>=(s); --i)
#define ll long long
#define ull unsigned long long
#define PII pair<int,int>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3fll
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
int dx[4]= {0,-1,0,1},dy[4]= {-1,0,1,0};
int dx8[8] = {0, 0, 1, -1, -1, -1, 1, 1}, dy8[8] = {1, -1, 0, 0, -1, 1, -1, 1};
/*
int get_bitz(unsigned int x){return _builtin_ctz(x);}
int get_bitzll(unsigned int x){return _builtin_ctzll(x);}
int get_bitcount(unsigned int x){return _builtin_popcount(x);}
int get_bitcountll(unsigned int x){return _builtin_popcountll(x);}
*/
int gcd(int a,int b)
{
return b? gcd(b,a%b) : a;
}
int lcm(int a,int b)
{
return a*b/gcd(a,b);
}
const int N=5e5+10,mod=9901;

ll qmi(ll a,ll k)
{
ll res=1;
a%=mod;//a可能比较大
while(k)
{
if(k&1) res=res*a%mod;
a=a*a%mod;
k>>=1;
}
return res;
}

ll sum(ll p,ll k)
{
if(k==1) return 1;
if(k%2==0) return (1+qmi(p,k/2))*sum(p,k/2)%mod;
return (sum(p,k-1)+qmi(p,k-1))%mod;
}

int main()
{
ios;
ll a,b;
cin>>a>>b;
//对a分解质因数
int res=1;
for(int i=2;i*i<=a;i++)
{
if(a%i==0)
{
int s=0;
while(a%i==0)
{
a/=i,s++;
}
res=res*sum(i,b*s+1)%mod;
}
}
if(a>1) res=res%mod*sum(a,b+1)%mod;
if(a==0) res=0;
cout<<res<<endl;
return 0;
}



Lazy_tiger
8个月前
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <list>
#include <limits.h>
#define il inline
#define pf printf
#define sf(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,e,s) for(int i=(e); i>=(s); --i)
#define ll long long
#define ull unsigned long long
#define PII pair<int,int>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3fll
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
int dx[4]= {0,-1,0,1},dy[4]= {-1,0,1,0};
int dx8[8] = {0, 0, 1, -1, -1, -1, 1, 1}, dy8[8] = {1, -1, 0, 0, -1, 1, -1, 1};
/*
int get_bitz(unsigned int x){return _builtin_ctz(x);}
int get_bitzll(unsigned int x){return _builtin_ctzll(x);}
int get_bitcount(unsigned int x){return _builtin_popcount(x);}
int get_bitcountll(unsigned int x){return _builtin_popcountll(x);}
*/
int gcd(int a,int b)
{
return b? gcd(b,a%b) : a;
}
int lcm(int a,int b)
{
return a*b/gcd(a,b);
}
const int N=110,mod=1e9+10;
int n,m;
int g[N][N],d[N][N];

void bfs()
{
memset(d,-1,sizeof(d));
queue<PII> q;
q.push({0,0});
d[0][0] = 0 ;

while(q.size())
{
PII t = q.front();
q.pop();
for(int i = 0 ;i < 4 ; i ++ )
{
int x = dx[i] + t.first , y = dy[i] + t.second;
if(x >= 0 && x < n && y >=0 && y < m && d[x][y] == -1 && g[x][y] == 0)
{
d[x][y] = d[t.first][t.second] + 1;
q.push({x,y});
}
}
}

cout<<d[n-1][m-1]<<endl;
return ;
}
int main()
{
ios;
cin>>n>>m;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>g[i][j];
}
}
bfs();
return 0;
}



Lazy_tiger
8个月前
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <list>
#include <limits.h>
#define il inline
#define pf printf
#define sf(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,e,s) for(int i=(e); i>=(s); --i)
#define ll long long
#define ull unsigned long long
#define PII pair<int,int>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3fll
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
int dx[4]= {0,-1,0,1},dy[4]= {-1,0,1,0};
int dx8[8] = {0, 0, 1, -1, -1, -1, 1, 1}, dy8[8] = {1, -1, 0, 0, -1, 1, -1, 1};
/*
int get_bitz(unsigned int x){return _builtin_ctz(x);}
int get_bitzll(unsigned int x){return _builtin_ctzll(x);}
int get_bitcount(unsigned int x){return _builtin_popcount(x);}
int get_bitcountll(unsigned int x){return _builtin_popcountll(x);}
*/
int gcd(int a,int b)
{
return b? gcd(b,a%b) : a;
}
int lcm(int a,int b)
{
return a*b/gcd(a,b);
}
const int N=110,mod=1e9+10;
int n;
int dg[N],udg[N],col[N];
char g[N][N];

void dfs(int u)
{
if(u==n)//表示已经搜索了n行
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cout<<g[i][j];
}
cout<<endl;
}
cout<<endl;
return ;
}
for(int i=0;i<n;i++)//选择了多少
{
if(!col[i]&&!dg[i+u]&&!udg[n-u+i])
{
col[i]=dg[i+u]=udg[n-u+i]=true;
g[u][i]='Q';
dfs(u+1);
g[u][i]='.';
col[i]=dg[i+u]=udg[n-u+i]=false;
}
}
}

int main()
{
ios;
cin>>n;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
g[i][j]='.';
}
}
dfs(0);
return 0;
}



Lazy_tiger
8个月前
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <list>
#include <limits.h>
#define il inline
#define pf printf
#define sf(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,e,s) for(int i=(e); i>=(s); --i)
#define ll long long
#define ull unsigned long long
#define PII pair<int,int>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3fll
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
int dx[4]= {0,-1,0,1},dy[4]= {-1,0,1,0};
int dx8[8] = {0, 0, 1, -1, -1, -1, 1, 1}, dy8[8] = {1, -1, 0, 0, -1, 1, -1, 1};
/*
int get_bitz(unsigned int x){return _builtin_ctz(x);}
int get_bitzll(unsigned int x){return _builtin_ctzll(x);}
int get_bitcount(unsigned int x){return _builtin_popcount(x);}
int get_bitcountll(unsigned int x){return _builtin_popcountll(x);}
*/
int gcd(int a,int b)
{
return b? gcd(b,a%b) : a;
}
int lcm(int a,int b)
{
return a*b/gcd(a,b);
}
const int N=2e6+10,mod=1e9+10;
int n;
int p[N];
bool st[N];

void dfs(int u)
{
if(u==n)
{
for(int i=0;i<n;i++)
{
cout<<p[i]<<" ";
}
cout<<endl;
return ;
}
for(int i=1;i<=n;i++)
{
if(!st[i])
{
st[i]=true;
p[u]=i;
dfs(u+1);
p[u]=0;
st[i]=false;
}
}
}
int main()
{
ios;
cin>>n;
dfs(0);
return 0;
}

`