Problem1 Preokret
第一题一定不是什么难题。
第一个问题在读入的时候判断当前时间是不是在1440及以前就行
第二个问题考虑离线处理，由于每个时刻只能最多发生1个事件那么就弄个桶记录每一个事件就行了。
水过T1。
Code：
# include <bits/stdc++.h>
using namespace std;
const int N=;
int a[N];
int A,B,T,rec1,rec2;
template <typename T>inline void read(T &x)
{
int w=,X=; char c=;
while (c<''||c>'') w|=c=='-',c=getchar();
while (c>=''&&c<='') X=(X<<)+(X<<)+(c^),c=getchar();
x=w?-X:X;
}
int main()
{
// freopen("Preokret.in","r",stdin);
// freopen("Preokret.out","w",stdout);
memset(a,-,sizeof(a));
read(A);
for (int i=;i<=A;i++) read(T),a[T]=;
read(B);
for (int i=;i<=B;i++) read(T),a[T]=;
int Ans1=,Ans2=,flag=-,s1=,s2=;
for (int i=;i<=;i++) {
if (a[i]==-) continue;
if (a[i]==) s1++; else s2++;
if (i<=) Ans1++;
if (flag==-) { flag=s1<s2; continue;}
if (s1>s2&&flag==) flag=,Ans2++;
else if (s1<s2&&flag==) flag=,Ans2++;
}
cout<<Ans1<<'\n'<<Ans2<<'\n';
return ;
}
Problem2 Kocka
这个题对于100%的数据一定不是O(n2)的构造，而是数学的判断。
我们可以简单考虑四种情况，我们记四个数组分别是left[],right[],up[],down[],
分别考虑四个数组元素值是x的时候代表什么含义，
以left[i]为例，left[i]=-1的时候表示第i行没有放东西，那么对应的right[i]必须也是-1否则构造不合法,而对于up[]和down[]无影响。
left[i]=x(x≠-1时)，那么意味着在(i,x+1)这个位置必须存在一个障碍物，那么从上面看下来可以看到的不能大于i-1吧，下面看上来不能超过n-i吧，右边看过来不能超过n-x-1吧。
对于 right[]和up[]和down[]同理。
这里需要注意在C++中up什么的可能是保留字，我Define了一下。
Code
# include <bits/stdc++.h>
# define fp(i,s,t) for (int i=s;i<=t;i++)
# define left Left
# define right Right
# define up Up
# define down Down
using namespace std;
const int N=1e5+;
int left[N],right[N],up[N],down[N],n;
inline void read(int &x)
{
int w=,X=; char c=;
while (c<''||c>'') w|=c=='-',c=getchar();
while (c>=''&&c<='') X=(X<<)+(X<<)+(c^),c=getchar();
x=w?-X:X;
}
bool work()
{
fp(i,,n) {
if (left[i]==-) {
if (right[i]==-) continue;
return ;
}
if (up[left[i]+]==-||up[left[i]+]>i-) return ;
if (down[left[i]+]==-||down[left[i]+]>n-i) return ;
if (right[i]==-||right[i]>n-left[i]-) return ;
}
fp(i,,n) {
if (up[i]==-) {
if (up[i]==-) continue;
return ;
}
if (left[up[i]+]==-||left[up[i]+]>i-) return ;
if (right[up[i]+]==-||right[up[i]+]>n-i) return ;
if (down[i]==-||down[i]>n-up[i]-) return ;
}
fp(i,,n) {
if (right[i]==-) {
if (left[i]==-) continue;
return ;
}
if (up[n-right[i]]==-||up[n-right[i]]>i-) return ;
if (down[n-right[i]]==-||down[n-right[i]]>n-i) return ;
if (left[i]==-||left[i]>n-right[i]-) return ;
}
fp(i,,n) {
if (down[i]==-) {
if (up[i]==-) continue;
return ;
}
if (left[n-down[i]]==-||left[n-down[i]]>i-) return ;
if (right[n-down[i]]==-||right[n-down[i]]>n-i) return ;
if (up[i]==-||up[i]>n-down[i]-) return ;
}
return ;
}
int main()
{
// freopen("Kocka.in","r",stdin);
// freopen("Kocka.out","w",stdout);
read(n);
fp(i,,n) read(left[i]);
fp(i,,n) read(right[i]);
fp(i,,n) read(up[i]);
fp(i,,n) read(down[i]);
puts(work()?"DA":"NE");
return ;
}
Problem3 Deblo
这个题是树上路径计数，初步搞搞O(n2log2 n)暴力还是搞得来的。
但是书上路径统计想到了淀粉质点分治暴力统计路径。
这里需要注意点分治的一般步骤：
每次在子树里面选定一个重心，考虑一条过重心的路径，统计这条边上的异或值。
这里用到异或的一个性质x xor y xor y=x，考虑以子树的根（不一定是重心）dfs下去找到根的xor前缀和
统计每个点的xor，那么就把01塞到桶里面就行了。
注意这个时候由于每一条路径一定过重心所以先把重心加入，其他的前缀和先xor一个重心，这样可以把重心的影响减去。
尤其注意先找这个点和其他点之间xor值然后再更新桶里面的值。
重心打标及时啊!一塞入就打标。
一开始先找重心可以快一点。。。
具体的可以看我的点分治blog例题1：https://www.cnblogs.com/ljc20020730/p/10347198.html
# include <bits/stdc++.h>
# define LL long long
# define fp(i,s,t) for (int i=s;i<=t;i++)
using namespace std;
const int N=1e5+;
const int MAXBIT=;
bool used[N];
int size[N],val[N],cnt[][MAXBIT],n;
struct rec{int pre,to;}a[*N];
int tot,head[N];
template <typename T>inline void read(T& t)
{
char c=getchar();t=;
while(c<''||c>'')c=getchar();
while(c>=''&&c<='')t=(t<<)+(t<<)+(c^),c=getchar();
}
template <typename T,typename... Args> inline void read(T& t, Args&... args)
{
read(t);read(args...);
}
void write(LL x)
{
if (x>) write(x/);
putchar(''+x%);
}
void writeln(LL x)
{
write(x);putchar('\n');
}
void adde(int u,int v)
{
a[++tot].pre=head[u];
a[tot].to=v;
head[u]=tot;
}
int Get_Root(int u,int fath,int S)
{
int pos=;
for (int i=head[u];i;i=a[i].pre) {
int v=a[i].to;
if (v==fath||used[v]) continue;
if (size[v]>size[pos]) pos=v;
}
if (pos!=&&size[pos]>=S/) return Get_Root(pos,u,S);
return u;
}
void Get_Dist(int u,int fath,int num)
{
num^=val[u]; size[u]=;
fp(i,,MAXBIT-)
cnt[(num & (<<i))>][i]++; for (int i=head[u];i;i=a[i].pre){
int v=a[i].to;
if (v==fath||used[v]) continue;
Get_Dist(v,u,num);
size[u]+=size[v];
}
}
LL ans=;
void Get_Ans(int u,int fath,int num)
{
num^=val[u];
fp(i,,MAXBIT-)
ans+=(LL) (<<i)*cnt[(num & (<<i))==][i];
for (int i=head[u];i;i=a[i].pre){
int v=a[i].to;
if (v==fath||used[v]) continue;
Get_Ans(v,u,num);
}
}
void solve(int u,int fath)
{
int root=Get_Root(u,fath,size[u]);
used[root]=;
memset(cnt,,sizeof(cnt));
fp(i,,MAXBIT-)
cnt[(val[root] & (<<i))>][i]++;
ans+=(LL)val[root];
for (int i=head[root];i;i=a[i].pre) {
int v=a[i].to;
if (used[v]) continue;
Get_Ans(v,,);
Get_Dist(v,,val[root]);
}
for (int i=head[root];i;i=a[i].pre) {
int v=a[i].to;
if (used[v]) continue;
solve(v,u);
}
}
int main()
{
read(n); fp(i,,n) read(val[i]);
int u,v;
fp(i,,n-)
read(u,v),adde(u,v),adde(v,u);
int rt=Get_Root(,,n);
Get_Dist(rt,,); solve(rt,);
writeln(ans);
return ;
}
Problem4 Maja
数据加强的三个点其实就是把大多数标程卡掉的点。
就是K不是偶数而是奇数的时候显然是不存在合法的一条路径的。
这点原题中没有说需要判断。（但是神奇的是没有卡WTF）
这道题显然K这么大不是搜索而是DP，
搜索的复杂度O(4K)太大了吧！！！ 而且每个点不止重复走1次。
考虑一条性质：假设从原点(A,B)走到(i,j)恰好走了K/2步然后必然会选择走回去是最优的吧。
这个显然。
然后考虑全局的最优，答案一定是一个循环组成的，就是不停地在某一条路上来回走。
这个也是显然的吧。
那么有余数怎么办？可以证明贪心的选取中点四周的一个Ci,j最大的来回走完余数就是这个点最优的。
这个可以反证？ 简单yy一下如果不这样选取那么你还不如走到你最终的中点继续循环呢！
然后就是一个DP+贪心的神仙题目了。
先K/=2，只考虑去，回来其实近似乘以2就行。（其实并不是乘以2）
设f[i][j][r]指的是从(A,B)走到(i,j)经过(i,j)有r次的最优解，那么显然是从四个方向走来的吧。
转移是f[i][j][r]=Max{f[x][y][r-1]}+c[i][j]（x,y指的是(i,j)四个相邻点）
回去就是f[i][j][r]+Max{f[x][y][r-1]}，那是Ci,j少记一次。
然后剩余的步数（只记去，此时K已经除以2）就是K-r，余数走的步数就是
(K-r)*(Max{c[x][y]}+c[i][j])
然后每次到(i,j)r次计算一下答案。
那个r一维可以滚存，r的取值范围是[0,Min(k,n*m)]
Code：
# include<bits/stdc++.h>
# define fp(i,s,t) for (int i=s;i<=t;i++)
# define inf (0x7f7f7f7f7fll)
# define int long long
using namespace std;
const int N=;
int f[N][N][],c[N][N];
int n,m,A,B,K,ans;
int Get_Max(int a,int b,int c,int d)
{
if (b>a) a=b;
if (c>a) a=c;
if (d>a) a=d;
return a;
}
template <typename T>inline void read(T& t)
{
char c=getchar();t=;
while(c<''||c>'')c=getchar();
while(c>=''&&c<='')t=(t<<)+(t<<)+(c^),c=getchar();
}
template <typename T,typename... Args> inline void read(T& t, Args&... args)
{
read(t);read(args...);
}
void write(int x)
{
if (x>) write(x/);
putchar(''+x%);
}
void writeln(int x)
{
write(x);putchar('\n');
}
signed main()
{
read(n,m,A,B,K);
if (K&) { puts("");exit();}
K=K>>;
fp(i,,n+) fp(j,,m+)
c[i][j]=f[i][j][]=f[i][j][]=-inf;
fp(i,,n) fp(j,,m) read(c[i][j]);
f[A][B][]=; ans=-inf;
fp (r,,min(K,n*m)) {
int now=r&;
int pst=now^;
fp(i,,n) fp(j,,m) {
int temp=Get_Max(f[i-][j][pst],f[i+][j][pst],f[i][j-][pst],f[i][j+][pst]);
f[i][j][now]=max(temp+c[i][j],-inf);
if (f[i][j][now]<) continue;
int Whole_Dist=f[i][j][now]+temp;
Whole_Dist+=(K-r)*(c[i][j]+Get_Max(c[i-][j],c[i+][j],c[i][j-],c[i][j+]));
ans=max(ans,Whole_Dist);
}
}
writeln(ans);
return ;
}
Problem5 Sunčanje
一道暴力的神仙T5，一看到数据范围就不想暴力的。
但是算算暴力的期望还是值得的。
先按照矩形右下角的x坐标排序，然后枚举每一个长方形，i，看看前面的长方形j是不是包含在i里面的，
被包含的必要条件是a[i].x-a[i].len<a[j].x对吧，不满足必要条件的那么前面也不满足必要条件，直接跳掉。
然后花四个图看看判包含。
(a[i].y>a[j].y&&a[i].y<a[j].y+a[j].wid)
||(a[i].y+a[i].wid>a[j].y&&a[i].y+a[i].wid<a[j].y+a[j].wid)
||(a[j].y>a[i].y&&a[j].y<a[i].y+a[i].wid)
||(a[j].y+a[j].wid>a[i].y&&a[j].y+a[j].wid<a[i].y+a[i].wid)
更新的时候注意看看谁在谁的下面（一定是初始标号小的放在下面！）
然后瞎加点优化就可以用pascal过4000ms时限了（而C++不行）
然后我就把第19个点的时限改成了6000ms，于是pascal和C++都过了
如果C++代码在XOJ上过不了的话那么加一行
# pragma G++ optimize(3)
Code C++
# pragma G++ optimize(3)
# include <bits/stdc++.h>
# define fp(i,s,t) for (int i=s;i<=t;i++)
using namespace std;
const int N=1e5+;
struct rec{
int x,y,len,wid,id;
}a[N];
int n;
bool ans[N];
inline int read()
{
int X=,w=; char c=;
while(c<''||c>'') {w|=c=='-';c=getchar();}
while(c>=''&&c<='') X=(X<<)+(X<<)+(c^),c=getchar();
return w?-X:X;
}
inline void qsort(int l,int r)
{
if (l==r) return;
int t=rand()%(r-l)+l;
swap(a[t],a[l]);
rec v=a[l]; int i=l,j=r;
while (i<j) {
while (i<j&&a[j].x>v.x) j--;
if (i<j) {a[i]=a[j];i++;} else break;
while (i<j&&a[i].x<v.x) i++;
if (i<j) {a[j]=a[i];j--;} else break;
}
a[i]=v;
if (l<j) qsort(l,j-);
if (i<r) qsort(i+,r);
}
signed main()
{
srand(time(NULL)*);
n=read();
fp(i,,n) {
a[i].x=read();a[i].y=read();a[i].len=read();a[i].wid=read();
a[i].x+=a[i].len;
a[i].id=i;
}
qsort(,n);
fp(i,,n) {
int j=i-;
while (j>=&&(a[i].x-a[i].len<a[j].x)) {
if ((a[i].y>a[j].y&&a[i].y<a[j].y+a[j].wid)
||(a[i].y+a[i].wid>a[j].y&&a[i].y+a[i].wid<a[j].y+a[j].wid)
||(a[j].y>a[i].y&&a[j].y<a[i].y+a[i].wid)
||(a[j].y+a[j].wid>a[i].y&&a[j].y+a[j].wid<a[i].y+a[i].wid))
{
if (a[i].id<a[j].id) ans[a[i].id]=;
else ans[a[j].id]=;
}
j--;
}
}
fp(i,,n)
if (ans[i]) putchar('N'),putchar('E'),putchar('\n');
else putchar('D'),putchar('A'),putchar('\n');
return ;
}
Code Pascal
VAR
n,i,j:int64; x,y,len,wid,poza,raspuns:array[..] of int64;
function Poz(a1,b1 : int64) : int64;
VAR aux,piv:int64;
Begin
piv:=x[a1];
while (a1 < b1) do
Begin
if (x[a1] > x[b1]) then Begin
aux:=x[a1]; x[a1]:=x[b1]; x[b1]:=aux;
aux:=y[a1]; y[a1]:=y[b1]; y[b1]:=aux;
aux:=len[a1]; len[a1]:=len[b1]; len[b1]:=aux;
aux:=wid[a1]; wid[a1]:=wid[b1]; wid[b1]:=aux;
aux:=poza[a1]; poza[a1]:=poza[b1]; poza[b1]:=aux; end;
if (piv = x[a1]) then b1:=b1 - else a1:=a1 + ;
end;
Poz:=a1;
end;
procedure Quick(a1,b1 : int64);
VAR k:int64;
Begin
if (a1 < b1) then
Begin
k:=Poz(a1,b1);
Quick(a1,k - );
Quick(k + ,b1);
end;
end;
Begin
Readln(n);
for i:= to n do
Begin
Readln(x[i],y[i],len[i],wid[i]);
x[i]:=x[i] + len[i];
poza[i]:=i;
end;
Quick(,n);
raspuns[]:=;
for i:= to n do
Begin
j:=i - ;
while (j > ) and (x[i] - len[i] < x[j]) do
Begin
if (((y[i] > y[j]) and (y[i] < y[j] + wid[j]))
or ((y[i] + wid[i] > y[j]) and (y[i] + wid[i] < y[j] + wid[j])))
or (((y[j] > y[i]) and (y[j] < y[i] + wid[i]))
or ((y[j] + wid[j] > y[i]) and (y[j] + wid[j] < y[i] + wid[i]))) then
Begin
if (poza[i] < poza[j]) then raspuns[poza[i]]:= else raspuns[poza[j]]:=;
end;
j:=j - ;
end;
end;
for i:= to n do
if (raspuns[i] = ) then Writeln('NE') else Writeln('DA');
END.