總結：…這場打的心累…
T3
題目大意：給出平面上n個點 ( x , y ) (x,y) (x,y)，求在給定的m個點中，到n個點的曼哈頓距離和最小的一個點；
( a , b ) (a,b) (a,b)到 ( c , d ) (c,d) (c,d)曼哈頓距離為: ∣ a ? c ∣ + ∣ b ? d ∣ |a-c|+|b-d| ∣a?c∣+∣b?d∣
顯然x和y可以分開處理…只看一維的話,就可離散化+開兩個bit處理解決了；將此操作也對y進行即可，
一個bit(a1)記錄當前位置的數出現次數，一個bit(a2)記錄當前位置的值的和；
那么統計答案比x小的數的
a
b
s
(
x
?
a
[
i
]
)
abs(x-a[i])
abs(x?a[i])就是
q
1
(
x
?
1
)
?
x
?
q
2
(
x
?
1
)
q1(x-1)*x-q2(x-1)
q1(x?1)?x?q2(x?1)，比x大的數類似做一遍即可，
將此操作對y也進行處理一遍，就可得到更新后的ans陣列，
代碼超長如下：
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define maxn 1000005
#define inf 1e18
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
inline ll read()
{
ll x=0,w=1; char c=getchar();
while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
return w==1?x:-x;
}
ll c1[maxn],c2[maxn],n,m,a[maxn],b[maxn],X[maxn],y[maxn];
ll cnt,p[maxn],ans[maxn],ax,ay;
inline void a1(int x,int val){for(int i=x;i<=cnt;i+=i&-i) c1[i]+=val;}
inline void a2(int x,int val){for(int i=x;i<=cnt;i+=i&-i) c2[i]+=val;}
inline ll q1(int x){ll res=0; for(int i=x;i;i-=i&-i) res+=c1[i]; return res;}
inline ll q2(int x){ll res=0; for(int i=x;i;i-=i&-i) res+=c2[i]; return res;}
int main()
{
freopen("t1.in","r",stdin);
n=read(); m=read();
rep(i,1,n) a[i]=read(),b[i]=read();
rep(i,1,m) X[i]=read(),y[i]=read();
rep(i,1,n) p[++cnt]=a[i];
rep(i,1,m) p[++cnt]=X[i];
sort(p+1,p+cnt+1); cnt=unique(p+1,p+cnt+1)-p-1;
rep(i,1,n)
{
int x=lower_bound(p+1,p+cnt+1,a[i])-p;
a1(x,1); a2(x,a[i]);
}
rep(i,1,m)
{
int x=lower_bound(p+1,p+cnt+1,X[i])-p;
ll tmp=q1(x-1)*X[i]-q2(x-1);
tmp+=(q2(n)-q2(x))-(n-q1(x))*X[i];
ans[i]+=tmp;
}
cnt=0;
rep(i,1,n+m) c1[i]=0,c2[i]=0;
rep(i,1,n) p[++cnt]=b[i];
rep(i,1,m) p[++cnt]=y[i];
sort(p+1,p+cnt+1); cnt=unique(p+1,p+cnt+1)-p-1;
rep(i,1,n)
{
int x=lower_bound(p+1,p+cnt+1,b[i])-p;
a1(x,1); a2(x,b[i]);
}
rep(i,1,m)
{
int x=lower_bound(p+1,p+cnt+1,y[i])-p;
ll tmp=q1(x-1)*y[i]-q2(x-1);
tmp+=(q2(n)-q2(x))-(n-q1(x))*y[i];
ans[i]+=tmp;
}
ll nw=inf;
rep(i,1,m)
{
if(ans[i]<nw) ax=X[i],ay=y[i],nw=ans[i];
}
cout<<ax<<" "<<ay<<endl;
return 0;
}
Java版：
import java.io.*;
import java.util.*;
public class zbr01
{
public static int n,m;
public static long c1[]=new long [200005];
public static long c2[]=new long [200005];
public static int X[]=new int [200005];
public static int y[]=new int [200005];
public static int a[]=new int [200005];
public static int b[]=new int [200005];
public static int p[]=new int [200005];
public static long ans[]=new long[100005];
public static int ax,ay;
public static void a1(int x,int val)
{
for(int i=x;i<=n+m;i+=i&-i) c1[i]+=val;
}
public static void a2(int x,int val)
{
for(int i=x;i<=n+m;i+=i&-i) c2[i]+=val;
}
public static long q1(int x)
{
long res=0;
for(int i=x;i!=0;i-=i&-i) res+=c1[i];
return res;
}
public static long q2(int x)
{
long res=0;
for(int i=x;i!=0;i-=i&-i) res+=c2[i];
return res;
}
public static void main(String args[])
{
Scanner S=new Scanner(System.in);
n=S.nextInt(); m=S.nextInt(); p[0]=10000000;
for(int i=1;i<=n;i++) {a[i]=S.nextInt(); b[i]=S.nextInt();}
for(int i=1;i<=m;i++) {X[i]=S.nextInt(); y[i]=S.nextInt();}
Map<Integer,Integer> mp = new HashMap<Integer,Integer>();
int cnt=0,c3=0;
for(int i=1;i<=n;i++) p[++cnt]=a[i];
for(int i=1;i<=m;i++) p[++cnt]=X[i];
Arrays.sort(p,1,cnt+1);
for(int i=1;i<=cnt;i++) if(p[i]!=p[i-1]) mp.put(p[i],++c3);
for(int i=1;i<=n;i++)
{
int x=mp.get(a[i]);
a1(x,1); a2(x,a[i]);
}
for(int i=1;i<=m;i++)
{
int x=mp.get(X[i]);
long tmp=q1(x-1)*X[i]-q2(x-1);
tmp+=(q2(n+m)-q2(x))-(n-q1(x))*X[i];
ans[i]+=tmp;
}
cnt=0; c3=0; mp.clear();
for(int i=1;i<=n+m;i++) {c1[i]=0; c2[i]=0;}
for(int i=1;i<=n;i++) p[++cnt]=b[i];
for(int i=1;i<=m;i++) p[++cnt]=y[i];
Arrays.sort(p,1,cnt+1);
for(int i=1;i<=cnt;i++) if(p[i]!=p[i-1]) mp.put(p[i],++c3);
for(int i=1;i<=n;i++)
{
int x=mp.get(b[i]);
a1(x,1); a2(x,b[i]);
}
for(int i=1;i<=m;i++)
{
int x=mp.get(y[i]);
long tmp=q1(x-1)*y[i]-q2(x-1);
tmp+=(q2(n+m)-q2(x))-(n-q1(x))*y[i];
ans[i]+=tmp;
}
long nw=ans[1]; ax=X[1]; ay=y[1];
for(int i=2;i<=m;i++)
{
if(ans[i]<nw)
{
ax=X[i]; ay=y[i]; nw=ans[i];
}
}
System.out.println(ax+" "+ay);
}
}
T4
題目大意：給出一顆權值為0/1的樹，單次操作可將該節點及和自己相鄰的節點進行翻轉(0變成1，1變成0)，問是否能將全部節點變成0.
n < = 5 e 5 n<=5e5 n<=5e5
由于某些奇怪的原因沒有提交這份代碼…正確性未知…感覺很對hhh
隨便選一個點進行dfs，設計狀態如下：
d
p
[
u
]
[
0
]
dp[u][0]
dp[u][0]為該點為0，子樹節點全為0的狀態是否可行；
d
p
[
u
]
[
1
]
dp[u][1]
dp[u][1]為改點為1，子樹節點全為0的狀態是否可行，
具體細節詳見代碼（
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
struct data_p{int hed,f[2],b;}pot[500005];
struct data_l{int to,nxt;}lin[1000005];
int t,n,top,ans;
void add_l(int a,int b){lin[++top].to=b;lin[top].nxt=pot[a].hed;pot[a].hed=top;}
void dp(int a,int fa)
{
int b;
pot[a].f[1]=pot[a].b^1;pot[a].f[0]=pot[a].b;
for(int i=pot[a].hed;i;i=lin[i].nxt)
{
b=lin[i].to;
if(b==fa)continue;
dp(b,a);
if(pot[b].f[1])pot[a].f[0]^=1;
else pot[a].f[1]^=1;
}
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);top=0;
for(int i=1;i<=n;i++)
{
pot[i].hed=0;
scanf("%d",&pot[i].b);
}
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add_l(x,y);add_l(y,x);
}
dp(1,1);
if((pot[1].f[0]==1||pot[1].f[1]==1))printf("YES\n");
else printf("NO\n");
}
return 0;
}
T2
題目大意：簽到的正常小模擬題…
求冪使用快速冪演算法即可（
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define maxn 1000005
#define inf 1e9
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
inline int read()
{
int x=0,w=1; char c=getchar();
while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
return w==1?x:-x;
}
const ll mod=1000000007;
inline ll pw(ll a,ll b)
{
ll ans=1,base=a;
while(b)
{
if(b&1) ans=(ans*base)%mod;
base=(base*base)%mod; b>>=1;
}
return ans;
}
int main()
{
freopen("t1.in","r",stdin);
int T=read();
while(T--)
{
ll n,m;
cin>>n>>m; char opt; cin>>opt;
if(opt=='+') printf("%lld\n",(n+m)%mod);
else if(opt=='-') printf("%lld\n",n-m);
else if(opt=='*') printf("%lld\n",(n*m)%mod);
else printf("%lld\n",pw(n,m));
}
return 0;
}
T1
題目大意：求一個字串的最小回圈節
l e n < = 1 e 8 len<=1e8 len<=1e8
kmp板子題，求出的nxt陣列就是長度最長的(前綴==后綴)的長度，那么最后考慮L-nxt[L]是否滿足條件即可，
代碼如下：
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define maxn 100000005
#define inf 1e9
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
inline int read()
{
int x=0,w=1; char c=getchar();
while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
return w==1?x:-x;
}
int nxt[maxn];
char s[maxn];
int main()
{
//freopen("t1.in","r",stdin);
scanf("%s",s+1); int l=strlen(s+1);
for(int i=2,k=0;i<=l;i++)
{
while(k&&s[i]!=s[k+1]) k=nxt[k];
if(s[i]==s[k+1]) k++;
nxt[i]=k;
}
int p=l-nxt[l]; if(l%p!=0) p=l;
rep(i,1,p) printf("%c",s[i]);
return 0;
}
END
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/99777.html
標籤：其他
下一篇：思科 GRE