解题报告……

A. Two Squares

签到题,枚举一个点,看是否都在两个矩形里。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
int a[4][2],b[4][2];
int main(){
int x_min=1e9, x_max=-1e9, y_min=1e9, y_max=-1e9;
for(int i=0;i<=3;i++){
scanf("%d%d",&a[i][0],&a[i][1]);
x_min=min(x_min,a[i][0]); x_max=max(x_max,a[i][0]);
y_min=min(y_min,a[i][1]); y_max=max(y_max,a[i][1]);
}
for(int i=0;i<=3;i++){
scanf("%d%d",&b[i][0],&b[i][1]);
}
double px=(b[0][0]+b[2][0])/2, py=(b[0][1]+b[2][1])/2, d=fabs(px-b[0][0])+fabs(py-b[0][1]);
for(int i=-100;i<=100;i++)
for(int j=-100;j<=100;j++)
if(fabs(i-px)+fabs(j-py)<=d&&x_min<=i&&i<=x_max&&y_min<=j&&j<=y_max) return puts("YES"), 0;
puts("NO");
return 0;
}

B. Open Communication

题意看上去很复杂,我看了半天才懂……

只要理解题意就行了,注意细节。如果某个人说的一对数都被配对了,大家就都不知道了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
int n1,n2,a[maxn][2],b[maxn][2];
int visa[maxn][2],visb[maxn][2];
int main(){
scanf("%d%d",&n1,&n2);
for(int i=1;i<=n1;i++){
scanf("%d%d",&a[i][0],&a[i][1]);
if(a[i][0]>a[i][1]) swap(a[i][0],a[i][1]);
}
for(int i=1;i<=n2;i++){
scanf("%d%d",&b[i][0],&b[i][1]);
if(b[i][0]>b[i][1]) swap(b[i][0],b[i][1]);
}
int cnt=0,res=0;
for(int i=1;i<=n1;i++)
for(int j=1;j<=n2;j++){
if(a[i][0]==b[j][0]&&a[i][1]==b[j][1]) continue;
for(int t1=0;t1<=1;t1++)
for(int t2=0;t2<=1;t2++)
if(a[i][t1]==b[j][t2]){
if(a[i][t1]!=res) cnt++;
res=a[i][t1];
visa[i][t1]++,visb[j][t2]++;
}
}
if(cnt==1) return printf("%d\n",res), 0;
for(int i=1;i<=n1;i++) if(visa[i][0]&&visa[i][1]) return puts("-1"), 0;
for(int i=1;i<=n2;i++) if(visb[i][0]&&visb[i][1]) return puts("-1"), 0;
return puts("0"), 0;
return 0;
}

C. Careful Maneuvering

中间有用的位置只有 \(O(n^2)\) ,直接爆枚。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n,m,a[105],b[105];
map <int,int> mp;
int k=0;
set<int> sl[20010],sr[20010],sll,srr;
set<int>::iterator it;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=m;i++) scanf("%d",&b[i]);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(mp[a[i]+b[j]]==0){
mp[a[i]+b[j]]=++k;
sl[k].insert(i);
sr[k].insert(j);
} else{
sl[mp[a[i]+b[j]]].insert(i);
sr[mp[a[i]+b[j]]].insert(j);
}
}
}
int ans=0;
if(k==1){
ans=sl[1].size()+sr[1].size();
printf("%d\n",ans);
return 0;
}
for(int i=1;i<=k;i++){
for(int j=i+1;j<=k;j++){
sll=sl[i]; srr=sr[i];
for(it=sl[j].begin();it!=sl[j].end();it++) sll.insert(*it);
for(it=sr[j].begin();it!=sr[j].end();it++) srr.insert(*it);
ans=max(ans,(int)(sll.size()+srr.size()));
}
}
printf("%lld\n",ans);
return 0;
}

D. Compute Power

很套路,首先分数规划,二分答案,然后转化成求 \(\sum a_i-mid*b_i\) 的最小然后 \(DP\) 求就好了。

我之前 \(zz\) , 没注意是严格小于。

所以 \(f(i,j,k)\) 表示处理到前 \(i\) 个,有 \(j\)\(a\)\(a_i\) 小且还没分配第二个,有 \(k\)\(a\) 等于 \(a_i\) 且还没分配第二个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
using namespace std;
struct data{
int x,y;
} a[55];
bool my_cmp(data A,data B){ return A.x>B.x; }
int n;
double f[55][55][55];
bool Check(double mid){
memset(f,0x43,sizeof(f)); double INF=f[0][0][0];
f[0][0][0]=0;
for(int i=0;i<=n-1;i++)
for(int j=0;j<=i;j++)
for(int k=0;j+k<=i;k++)
if(f[i][j][k]<INF){
if(i==0||a[i].x!=a[i+1].x){
if(j+k) f[i+1][j+k-1][0]=min(f[i+1][j+k-1][0],f[i][j][k]);
f[i+1][j+k][1]=min(f[i+1][j+k][1],f[i][j][k]+a[i+1].x-mid*a[i+1].y);
} else{
if(j) f[i+1][j-1][k]=min(f[i+1][j-1][k],f[i][j][k]);
f[i+1][j][k+1]=min(f[i+1][j][k+1],f[i][j][k]+a[i+1].x-mid*a[i+1].y);
}
}
double res=INF;
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++) res=min(res,f[n][i][j]);
return res<0;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i].x);
for(int i=1;i<=n;i++) scanf("%d",&a[i].y);
sort(a+1,a+1+n,my_cmp);
double L=0,R=1e10;
while(R-L>1e-4){
double mid=(L+R)/2;
if(Check(mid)) R=mid; else L=mid;
}
printf("%.0f\n",ceil(L*1000));
return 0;
}

E. Nikita and Order Statistics

我完了 \(FFT\) 套路都不会。

我们要求 \(sum_i-sum_j=k\) 的方案,即 \([x-y=k] cnt(x)*cnt(y)\) 。直接卷积…..

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const double PI=acos(-1);
const int maxn=1000005;
struct E{
double r,i;
E(double t1=0,double t2=0){ r=t1; i=t2; }
};
E operator + (const E &A,const E &B){ return E(A.r+B.r,A.i+B.i); }
E operator - (const E &A,const E &B){ return E(A.r-B.r,A.i-B.i); }
E operator * (const E &A,const E &B){ return E(A.r*B.r-A.i*B.i,A.r*B.i+A.i*B.r); }
int rev[maxn];
void get_rev(int n){
int t=0; while((1<<t)<n) t++;
for(int i=1;i<=n-1;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<t-1);
}
void FFT(E a[],int n,int k){
for(int i=0;i<=n-1;i++) if(i<rev[i]) swap(a[i],a[rev[i]]);
for(int m=2;m<=n;m<<=1){
E wm(cos(PI*2/m),(k?1:-1)*sin(PI*2/m));
for(int i=0;i<=n-1;i+=m){
E w=1,t0,t1;
for(int j=0;j<=(m>>1)-1;j++,w=w*wm)
t0=a[i+j], t1=a[i+j+(m>>1)]*w, a[i+j]=t0+t1, a[i+j+(m>>1)]=t0-t1;
}
}
if(k==0) for(int i=0;i<=n-1;i++) a[i].r/=n;
}
E A[maxn],B[maxn];
int n,K,N,sum[maxn];
int main(){
scanf("%d%d",&n,&K);
A[0].r+=1; B[n].r+=1;
for(int i=1;i<=n;i++){
int x; scanf("%d",&x);
sum[i]=sum[i-1]+(x<K);
A[sum[i]].r+=1; B[n-sum[i]].r+=1;
}
N=1; while(N<(n<<1)+1) N<<=1; get_rev(N);
// for(int i=0;i<=N-1;i++) printf("%d ",(int)A[i].r); printf("\n");
//for(int i=0;i<=N-1;i++) printf("%d ",(int)B[i].r); printf("\n");
FFT(A,N,1); FFT(B,N,1);
for(int i=0;i<=N-1;i++) A[i]=A[i]*B[i];
FFT(A,N,0);
printf("%lld ",((LL)(A[n].r+0.5)-n)>>1);
for(int i=1;i<=n;i++) printf("%lld ",(LL)(A[n+i].r+0.5));
return 0;
}

F. The Moral Dilemma

占坑……