2015-2016 Petrozavodsk Winter Training Camp, Nizhny Novgorod SU Contest
B. Forcefield
题意
给你一维平面上n个镜子，镜子的朝向有正面和背面，如果光束从正面穿过，会摧毁镜子，并且光束会反向；如果从背面穿过的话，什么都不会发生。
光束一开始从X位置，射向0点，然后你人在0点，会反射光束。
问你要破坏所有镜子，人需要反弹光束多少次。
数据范围100000
题解
其实模拟就好了，击破镜子的顺序就那么一种。
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+6;
const int inf = 1e9+1;
set<int> s1,s2;
int n,x[maxn],p[maxn];
set<int>::iterator it;
int main()
{
scanf("%d%d",&n,&x[0]);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&x[i],&p[i]);
if(p[i]==1)s1.insert(x[i]);
if(p[i]==0)s2.insert(x[i]);
}
s2.insert(0);
s1.insert(0);
s2.insert(inf);
s1.insert(inf);
int now = x[0],flag=2;
int ans = 0;
while(1)
{
if(flag==2){
int pos = *--s2.lower_bound(now);
if(pos==0){
ans++;
now=pos;
}
else{
s2.erase(pos);
now=pos;
}
flag=1;
}else{
int pos = *s1.upper_bound(now);
if(pos==inf){
if(s1.size()==2&&s2.size()==2)
break;
printf("-1\n");
return 0;
}else{
s1.erase(pos);
now=pos;
}
flag=2;
}
}
cout<<ans<<endl;
}
C.Missing Part
题意
给你一个串S，这个S是环状的，给你另外一个字符串S1。
给你大写的ABCDE和小写的abcde，然后你需要定义一种对应关系，使得失配数最小。
题解
假设只有两种字符，那么就是FFT了。
然后这个是5个嘛，最粗鲁的做法是120个FFT。
优化一下 就是25个FFT就好了。
队友写的，实验细节不知道。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e4 + 50;
char s1[maxn << 1],s2[maxn];
int n ,ans,f[15],use[15];
vector < int > pos[5] , ano[5];
const double PI = acos(-1.0);
//复数结构体
struct Complex
{
double r,i;
Complex(double _r = 0.0,double _i = 0.0)
{
r = _r; i = _i;
}
Complex operator +(const Complex &b)
{
return Complex(r+b.r,i+b.i);
}
Complex operator -(const Complex &b)
{
return Complex(r-b.r,i-b.i);
}
Complex operator *(const Complex &b)
{
return Complex(r*b.r-i*b.i,r*b.i+i*b.r);
}
};
/*
* 进行FFT和IFFT前的反转变换。
* 位置i和 （i二进制反转后位置）互换
* len必须去2的幂
*/
void change(Complex y[],int len)
{
int i,j,k;
for(i = 1, j = len/2;i < len-1; i++)
{
if(i < j)swap(y[i],y[j]);
//交换互为小标反转的元素，i<j保证交换一次
//i做正常的+1，j左反转类型的+1,始终保持i和j是反转的
k = len/2;
while( j >= k)
{
j -= k;
k /= 2;
}
if(j < k) j += k;
}
}
/*
* 做FFT
* len必须为2^k形式，
* on==1时是DFT，on==-1时是IDFT
*/
void fft(Complex y[],int len,int on)
{
change(y,len);
for(int h = 2; h <= len; h <<= 1)
{
Complex wn(cos(-on*2*PI/h),sin(-on*2*PI/h));
for(int j = 0;j < len;j+=h)
{
Complex w(1,0);
for(int k = j;k < j+h/2;k++)
{
Complex u = y[k];
Complex t = w*y[k+h/2];
y[k] = u+t;
y[k+h/2] = u-t;
w = w*wn;
}
}
}
if(on == -1)
for(int i = 0;i < len;i++)
y[i].r /= len;
}
int len = 131072;
Complex X[131075],Y[131075];
int ret[5][5][maxn];
void predeal(){
for(int i = 0 ; i < 5 ; ++ i)
for(int j = 0 ; j < 5 ; ++ j){
memset( X , 0 , sizeof( X ) );
memset( Y , 0 , sizeof( Y ) );
int x = i , y = j;
for(auto it : pos[i]) X[it+1].r++;
for(auto it : ano[y]) Y[n-it].r++;
fft( X , len , 1 );
fft( Y , len , 1 );
for(int j = 0 ; j < len ; ++ j) X[j] = X[j] * Y[j];
fft( X , len , -1 );
for(int k = n + 1 ; k <= 2 * n ; ++ k) ret[i][j][k - n] += (int)(X[k].r + 0.5);
}
}
void cal_ans(){
for(int i = 1 ; i <= n ; ++ i){
int sum = 0;
for(int j = 0 ; j < 5 ; ++ j)
sum += ret[j][f[j]][i];
ans = max( ans , sum );
}
}
void DFS( int x ){
if( x == 5 ){
cal_ans();
}else{
for(int i = 0 ; i < 5 ; ++ i)
if(!use[i]){
f[x] = i;
use[i] = 1;
DFS( x + 1 );
use[i] = 0;
}
}
}
int main(int argc , char * argv[] ){
freopen("in.txt","r",stdin);
scanf("%s%s",s1,s2);
n=strlen(s1);
for(int i = 0 ; i < n ; ++ i) s1[i + n] = s1[i];
for(int i = 0 ; i < (n * 2) ; ++ i) pos[s1[i] - 'A'].push_back( i );
for(int i = 0 ; i < n ; ++ i) ano[s2[i] - 'a'].push_back( i );
predeal();
DFS( 0 );
printf("%d\n",n-ans);
return 0;
}
The Jedi Killer
题意
平面上给你三个点，然后给你三条线段的长度，两条为lg，一条为lm。
三条线段的一个端点都在同一个位置，且lg垂直于lm。
问你这三个线段是否能够覆盖题目所给的三个点。
题解
丝薄题，XJB判一判就好了。
就三种情况，lm穿过两个点，lg穿过两个点，或者三点共线。
判判判就好了。
代码
#include<bits/stdc++.h>
using namespace std;
struct point
{
long long x,y;
}p[3];
long long cross(point p1,point p2,point p0)
{
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
long long dist2(point p1,point p2)
{
return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
}
void solve()
{
long long lg,lm;
cin>>lm>>lg;
for(int i=0;i<3;i++)
cin>>p[i].x>>p[i].y;
if(cross(p[0],p[1],p[2])==0)
{
long long tmp=max(lm*lm,lg*lg*4LL);
if(dist2(p[0],p[1])<=tmp&&dist2(p[1],p[2])<=tmp&&dist2(p[2],p[0])<=tmp)
printf("YES\n");
else
printf("NO\n");
return ;
}
for(int i=0;i<3;i++)
{
for(int j=i+1;j<3;j++)
{
for(int k=0;k<3;k++)
if(k!=i&&k!=j)
{
int flag=1;
long long a=p[i].y-p[j].y,b=p[j].x-p[i].x;
long long c=-a*p[i].x-b*p[i].y;
long long tmp=(a*p[k].x+b*p[k].y+c)*(a*p[k].x+b*p[k].y+c);
if(lm*lm*(a*a+b*b)<tmp) flag=0;
if(dist2(p[i],p[k])*(a*a+b*b)-tmp>lg*lg*(a*a+b*b)) flag=0;
if(dist2(p[j],p[k])*(a*a+b*b)-tmp>lg*lg*(a*a+b*b)) flag=0;
if(flag)
{
printf("YES\n");
return ;
}
flag=1;
if((dist2(p[i],p[j])+dist2(p[i],p[k])-dist2(p[j],p[k]))>0&&(dist2(p[i],p[j])+dist2(p[j],p[k])-dist2(p[i],p[k]))>0) flag=0;
if(lg*lg*(a*a+b*b)<tmp) flag=0;
if(dist2(p[i],p[k])*(a*a+b*b)-tmp>lm*lm*(a*a+b*b)) flag=0;
if(dist2(p[j],p[k])*(a*a+b*b)-tmp>lm*lm*(a*a+b*b)) flag=0;
if(flag)
{
printf("YES\n");
return ;
}
}
}
}
printf("NO\n");
}
int main()
{
int t;
scanf("%d",&t);
while(t--)solve();
return 0;
}
G. Youngling Tournament
题意
给你n个数，然后从大到小排序，如果这个数不小于他后面的数的和，那么这个数就是胜利者。
单点修改，问你每次胜利者有多少个。
题解
其实就是问你f[i]+sum[i]>=sum[n]的有多少个。
实际上就是区间修改+单点修改+查询区间第k大。
分块莽莽莽，然后再调一调常数就好了。
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+7;
inline long long read()
{
long long 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*10+ch-'0';ch=getchar();}
return x*f;
}
int n,N,m,num,belong[maxn],x[maxn],block,l[maxn],r[maxn],flag[maxn],p[maxn];
long long a[maxn],val[maxn],c[maxn];
long long sum[maxn],B[2000];
long long d[maxn];
map<long long,int> H;
int use[maxn],cnt;
vector<int>E[maxn];
int getid(long long x)
{
if(H[x])return H[x];
if(!H[x])H[x]=++cnt;
return H[x];
}
vector<long long> V;
void build()
{
N=V.size();
block=sqrt(N/2);
num=N/block;if(N%block)num++;
for(int i=1;i<=num;i++)
l[i]=(i-1)*block+1,r[i]=i*block;
r[num]=N;
for(int i=1;i<=N;i++)
belong[i]=(i-1)/block+1;
int tot = 1;
for(int i=1;i<=N;i++)
E[getid(a[i])].push_back(i);
for(int i=1;i<=n;i++)
flag[E[getid(c[i])][use[getid(c[i])]++]]=1;
}
void build(int l,int r)
{
int id=belong[l];B[id]=0;
for(int i=l;i<=r;i++)d[i]=0,sum[i]=0;
for(int i=l;i<=r;i++)
{
if(i!=l)sum[i]=sum[i-1];
if(flag[i]==1){
sum[i]+=a[i];
B[id]+=a[i];
d[i]=a[i]+sum[i];
}else{
d[i]=-1e9;
}
}
sort(d+l,d+r+1);
}
void query()
{
long long Sum = 0;
for(int i=1;i<=num;i++)
Sum+=B[i];
long long tmp = 0;
int ans = 0;
for(int i=1;i<=num;i++)
{
int L=l[i],R=r[i],Ans=r[i]+1;
while(L<=R)
{
int mid=(L+R)/2;
if(d[mid]+tmp>=Sum)Ans=mid,R=mid-1;
else L=mid+1;
}
ans+=(r[i]-Ans+1);
tmp+=B[i];
}
printf("%d\n",ans);
}
int main()
{
//freopen("1.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
a[i]=read();c[i]=a[i];
V.push_back(a[i]);
}
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
p[i]=read();val[i]=read();
V.push_back(val[i]);
}
sort(V.begin(),V.end());
reverse(V.begin(),V.end());
for(int i=0;i<V.size();i++)
a[i+1]=V[i];
build();
for(int i=1;i<=num;i++)
build(l[i],r[i]);
query();
for(int i=1;i<=m;i++)
{
int pos = E[getid(c[p[i]])][--use[getid(c[p[i]])]];
flag[pos]=0;
build(l[belong[pos]],r[belong[pos]]);
c[p[i]]=val[i];
pos=E[getid(c[p[i]])][use[getid(c[p[i]])]++];
flag[pos]=1;
build(l[belong[pos]],r[belong[pos]]);
query();
}
}
H. Garland Checking
题意
强制在线，给你一棵树
三个操作：
连接a，b
切掉a，b
查询a，b之间是否有边。
题解
裸LCT
代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 200010;
struct Node {
Node *ch[2], *p; int size, value;
bool rev;
Node(int t = 0);
inline bool dir(void) {return p->ch[1] == this;}
inline void SetC(Node *x, bool d) {
ch[d] = x; x->p = this;
}
inline void Rev(void) {
swap(ch[0], ch[1]); rev ^= 1;
}
inline void Push(void) {
if (rev) {
ch[0]->Rev();
ch[1]->Rev();
rev = 0;
}
}
inline void Update(void) {
size = ch[0]->size + ch[1]->size + 1;
}
}Tnull, *null = &Tnull, *fim[MAXN];
// 要记得额外更新null的信息
Node::Node(int _value){ch[0] = ch[1] = p = null; rev = 0;}
inline bool isRoot(Node *x) {return x->p == null || (x != x->p->ch[0] && x != x->p->ch[1]);}
inline void rotate(Node *x) {
Node *p = x->p; bool d = x->dir();
p->Push(); x->Push();
if (!isRoot(p)) p->p->SetC(x, p->dir()); else x->p = p->p;
p->SetC(x->ch[!d], d);
x->SetC(p, !d);
p->Update();
}
inline void splay(Node *x) {
x->Push();
while (!isRoot(x)) {
if (isRoot(x->p)) rotate(x);
else {
if (x->dir() == x->p->dir()) {rotate(x->p); rotate(x);}
else {rotate(x); rotate(x);}
}
}
x->Update();
}
inline Node* Access(Node *x) {
Node *t = x, *q = null;
for (; x != null; x = x->p) {
splay(x); x->ch[1] = q; q = x;
}
splay(t); //info will be updated in the splay;
return q;
}
inline void Evert(Node *x) {
Access(x); x->Rev();
}
inline void link(Node *x, Node *y) {
Evert(x); x->p = y;
}
inline Node* getRoot(Node *x) {
Node *tmp = x;
Access(x);
while (tmp->Push(), tmp->ch[0] != null) tmp = tmp->ch[0];
splay(tmp);
return tmp;
}
// 一定要确定x和y之间有边
inline void cut(Node *x, Node *y) {
Access(x); splay(y);
if (y->p != x) swap(x, y);
Access(x); splay(y);
y->p = null;
}
inline Node* getPath(Node *x, Node *y) {
Evert(x); Access(y);
return y;
}
inline void clear(void) {
null->rev = 0; null->size = 0; null->value = 0;
}
int judge(Node *x,Node *y)
{
while(x->p!=null)x = x->p;
while(y->p!=null)y = y->p;
if(x!=y)return 0;
return 1;
}
int main()
{
clear();
int n;
cin>>n;
for(int i=1;i<=n;i++)
fim[i] = new Node();
string c;
int u,v;
while(1)
{
cin>>c;
if(c[0]=='E')break;
cin>>u>>v;
if(c[0]=='T')
{
if(judge(fim[u],fim[v]))
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
else if(c[0]=='C')
link(fim[u],fim[v]);
else
cut(fim[u],fim[v]);
}
}