10.29 FJ四校联考

//四校联考Rank 16 感觉很滋磁（虽然考的时候抱怨厦门一中出的数学题很NOIP///）

圈地

【问题描述】

n根长度不一定相同的木棍，至多可以对其中一根切一刀，然后用其中的任意根围一个三角形，求三角形的最大面积。设面积为S，输出16*S^2对998244353取模后的答案。特别地，无解输出-1。

注：退化的三角形（面积为零）不被认为是三角形，答案应该为-1。

【输入文件】

输入文件为tri.in。

输入文件第一行包含两个正整数n和998244353。

第二行包含n个正整数，表示每根木棍的长度。

【输出文件】

输出文件为tri.out。

一行，即16*S^2 mod 998244353。

【输入输出样例】

tri.in

tri.out

1 2 3 4

360

【数据规模和约定】

对于20%的数据，满足ai<=1000。

对于另外30%的数据，满足n≤20。

对于100%的数据，满足1≤n≤40，1<=ai<=5*10^7。

Solution：

　　样例解释：3 3.5 3.5

　　　　　　 3 1+2+0.5 3.5 （4切成3.5和0.5）

　　　　　　由于最多只有一个木棍被切开，一定存在至少一条边是完全由未被切过的木棍组成的。设这条边的长度为x，设另外两条边的长度之和为y，此时另一个定点的轨迹为一个椭圆，当两条边的长度相等时面积最大。而两条边长度相等时，长度和越长面积越大。所以剩下的两条边长度为总长(l-x)/2,设一边为a。则三角形三边长度为a、a、l-2a，面积S=1/2*x*sqrt(a^2-x^2/4)。16*S^2=x^2*(4a^2-x^2)=(l-2a)^2*[4a^2-(l-2a)^2]=(2a-l)^2*(4a-l)*l。a的范围是(l/4,l/2)。

　　　　　　求导得导函数为8(2a-l)*(3a-l)*l，原函数在(l/4,l/3)单增，(l/3,l/2)单减。所以目标变成求最接近l/3的两个（一个小于l/3，一个大于）值，判断大小。由于只有l-2a是可枚举的，于是问题转换成了求最接近l/3的两个值。

　　　　　　判断的时候,通过做差可以将比较的函数降到两次，就不会炸longlong了。当然也可以求对数直接判断。　　

　　　　　　由于n比较小，权值比较大，一个比较简单的想法是求出所有可以拼出的长度，然后排序。基数排序可能可以过，复杂度2^n*n。另一种做法是，由于元素是由每个数选或不选决定的。考虑前i个的所有情况已经考虑，可以用归并排序的做法处理第i+1个。这样总复杂度还是2^n。

Other：

　　很伤心输出“-1”没有分数...（数据强啊）。

Code：

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 typedef long long ll;
 5 const int N = 40+10,M = 1048576+10,mod = 998244353;
 6 
 7 ll read(){
 8     ll x = 0;char ch = getchar();
 9     while (ch < '0' || '9' < ch) ch = getchar();
10     while ('0' <= ch && ch <= '9') x = x * 10 + ch - '0',ch = getchar();
11     return x;
12 }
13 
14 ll sum;
15 ll b[M],c[M],d[M],a[N];
16 int n,n2,lenb,lenc;
17 void solve();
18 ll check(ll,ll);
19 int main(){
20     freopen("tri.in","r",stdin);
21     freopen("tri.out","w",stdout);
22     n = read();n2 = n/2;sum = 0;
23     for (int i = 1;i <= n;i++) {
24         a[i] = read();
25         sum += a[i];
26     }
27     if (n == 1) printf("-1
");
28     else if (n == 2 && a[1] == a[2]) printf("-1
");
29     else solve();
30     return 0;
31 }
32 void solve(){
33     lenb = 1;lenc = 1;
34     for (int i = 1;i <= n2;i++){
35         for (int j = 0;j < lenb;j++){
36             d[j] = b[j];
37             d[j+lenb] = b[j]+a[i];
38         }
39         int u = 0,v = lenb,w = 0;
40         while (u < lenb && v < lenb+lenb){
41             if (d[u]<d[v]) b[w++] = d[u++];
42             else b[w++] = d[v++];
43         }
44         while (u < lenb) b[w++] = d[u++];
45         while (v < lenb+lenb) b[w++] = d[v++];
46         lenb = w;
47     }
48     for (int i = n2+1;i <= n;i++){
49         for (int j = 0;j < lenc;j++){
50             d[j] = c[j];
51             d[j+lenc] = c[j]+a[i];
52         }
53         int u = 0,v = lenc,w = 0;
54         while (u < lenc && v < lenc+lenc){
55             if (d[u]<d[v]) c[w++] = d[u++];
56             else c[w++] = d[v++];
57         }
58         while (u < lenc) c[w++] = d[u++];
59         while (v < lenc+lenc) c[w++] = d[v++];
60         lenc = w;
61     }
62 //    for(int i = 0;i < lenb;i++) cout << b[i]<<' ';cout<<endl;
63 //    for(int i = 0;i < lenc;i++) cout << c[i]<<' ';cout<<endl;        
64 
65 
66     ll m = sum/3,low = 0,upp = sum;
67     int tail = lenc;
68     for (int i = 0;i < lenb;i++){
69         while (tail && c[tail-1]+b[i] > m) tail--;
70         if (c[tail]+b[i] > m) upp = min(upp,c[tail]+b[i]);
71         if (tail) low = max(low,c[tail-1]+b[i]);
72     }
73 //    cout <<low<<' '<<upp<<endl;
74     ll ans = check(low,upp);
75     printf("%lld
",ans);
76 }
77 ll check(ll x,ll y){
78     ll ansx = x%mod*x%mod*(sum-x*2)%mod,ansy = y%mod*y%mod*(sum-y*2)%mod; 
79     if (x == 0 && y >= (sum+1)/2) return -1;
80     if (x == 0) return ansy%mod*sum%mod;
81     if (y >= (sum+1)/2) return ansx%mod*sum%mod;
82     ll delta = sum*(x+y)-x*y*2-x*x*2-y*y*2;
83 //    cout << delta<<endl;
84     if (delta > 0) return ansy*sum%mod;
85     else return ansx*sum%mod;
86 }

切糕

【问题描述】

求用m个n-1维平面最多能将一个n维空间分成多少份。多组询问。答案对998244353取模。

【输入文件】

输入文件为cut.in。

第一行为一个正整数T，表示询问个数。

接下来T行，每行两个整数n和m。

【输出文件】

输出文件为cut.out。

T行，每行一个整数即答案对998244353取模后的结果。

【输入输出样例】

cut.in

cut.out

3 3

2 3

1 1

【数据规模和约定】

对于30%的数据，满足n≤2。

对于50%的数据，满足n≤3。

对于100%的数据，满足1≤T≤10^5,1≤n、m≤3000。

Solution：

　　暴力推公式，只猜想，不验证！

ans(n,m)= C(n,0)+C(n,1)+C(n,2)+…+C(n,m)。

　　官方证明：

　　二维比较好考虑。设前k个已经切好，考虑k+1个，则最多会被分成k+1段。而每段会把每个区域都分成两份，所以增加了k+1个。

　　//应该比较好证明，题解表示数学归纳法可证。

　　三维的情况是类似的。考虑到第k+1个平面最多会被分成f_k个部分（f为二维情况下的答案），递推式显而易见。

　　更高维度的情况是类似的。递推式也很显然。复杂度O(n*m)。　

Code：

 1 #include<cstdio>
 2 #define MODE 998244353
 3 #define MAXN 3005
 4 using namespace std;
 5 int T;
 6 int C[MAXN+5][MAXN+5];
 7 inline void Initial(){ 
 8     for(int i=0;i<=MAXN;++i){C[0][i]=0; C[i][0]=1;} 
 9     for(int i=1;i<=MAXN;++i) 
10         for(int j=1;j<=MAXN;++j) 
11             C[i][j]=(C[i-1][j]+C[i-1][j-1])%MODE; 
12     for(int i=1;i<=MAXN;++i)
13         for(int j=1;j<=MAXN;++j)
14             C[i][j]+=C[i][j-1]%MODE,C[i][j]%MODE;
15 } 
16 int main(){
17     freopen("cut.in","r",stdin);
18     freopen("cut.out","w",stdout);
19     Initial();
20     scanf("%d",&T);
21     while(T--){
22         int n,m;scanf("%d%d",&n,&m);
23         printf("%d
",C[m][n]%MODE);
24     }
25     return 0;
26 }

选址

【问题描述】

一个有n栋房子的街道，房子从1到n标号。一开始1和n都有住人。接下来陆续有人按下述规则入住：

设新来的人的房子编号为x，则对于任意未住人的房子y，则x到原先有住人的房子的距离的最小值满足比y到其他原先有住人的房子的距离的最小值大或者相等且x<y。

现在询问街道中的第m位居民房子的编号。保证m大于2。

【输入文件】

输入文件为adr.in。

一行两个整数，n和m。

【输出文件】

输出文件为adr.out。

一行一个整数，即第m位居民房子的编号。

【输入输出样例】

adr.in	adr.out
6 4	2
39 3	20

【样例解释】

样例1中，第三个人住3，因为3和4对应的值都是2，而3<4。第四个人住2，因为2、4、5对应的值都是1。

样例2中，第三个人住20。

【数据规模和约定】

对于30%的数据，满足n、m≤1000。

对于60%的数据，满足n、m≤10^9。

对于100%的数据，满足1≤n、m≤10^18。

Solution：　

　　cf815E。　　

　　先考虑一个有瑕疵的结论：

　　所有空区间的长度都只有不超过两种可能。且一定是x和x+1。这里以一个空房子为一个单位长度。（准确的说是4种，还有两种是下一个阶段的x’和x'+1）

　　这个结论在大多数时候都是对的，除非在这一步就结束了或者长度小于4。于是，我们可以用记录区间中两个长度是多少和个数来快速计算中间的步骤。

　　递归到最后，我们要求出答案的相对位置，然后在回溯的过程中更新相对位置；或者另外写一个求答案的函数，由于路径已知，所以可以顺着递归结构每层求出对答案的贡献。

　　这个做法有不少细节问题：

　　1.要判断答案是在x中还是在x+1中，计算公式是不同的。

　　2.存在只有一种长度的情况。

　　3.当长度小于4时，要特殊处理。如只有2和3时，先全部在3中间，变成1和2，然后按从左到右的顺序依次填。

Code：

 1 #include<cstdio>
 2 #include<cstring>
 3 #define MAXN 1005
 4 using namespace std;
 5 unsigned int dis[MAXN];
 6 int n,m;
 7 inline void change(int i){
 8     for(int j=0;i-j>=1;j++)
 9         if(dis[i-j]>j) dis[i-j]=j;
10         else break;
11     for(int j=1;i+j<=n;j++)
12         if(dis[i+j]>j) dis[i+j]=j;
13         else break;
14 }
15 int main(){
16     freopen("adr.in","r",stdin);
17     freopen("adr.out","w",stdout);
18     scanf("%d%d",&n,&m);
19     memset(dis,0xff,sizeof(dis));
20     change(1),change(n);
21     for(int i=3;i<=m;i++){
22         int x=0,type=-1;
23         for(int j=1;j<=n;j++) if(dis[j]>x) x=dis[j],type=j;
24         change(type);
25         if(i==m) printf("%d",type);
26     }
27     return 0;
28 }

30分暴力

  1 #include <bits/stdc++.h>
  2 
  3 using namespace std;
  4 
  5 typedef long long ll;
  6 
  7 
  8 ll n,k,ans,sum,half;
  9 int ed,tip;
 10 void solve(ll,ll,ll,ll,ll,int d);
 11 void getans(ll,int);
 12 bool check(ll,int);
 13 ll getsum(ll,ll,ll,ll,int);
 14 int main(){
 15        freopen("adr.in","r",stdin);
 16     freopen("adr.out","w",stdout);
 17     scanf("%lld%lld",&n,&k);
 18     if (k == 1) puts("1"); 
 19     else if (k == 2) printf("%lld
",n);
 20     else {
 21         k -= 2;
 22         solve(0,0,n-2,1,k,1);
 23 //        cout << sum<<' '<<half<<' '<<k<<endl;
 24 //        cout << tip<<endl;
 25         getans(n-2,1);
 26         printf("%lld
",ans+1);
 27     }
 28     return 0; 
 29 }
 30 void solve(ll a,ll ax,ll b,ll bx,ll k,int d){
 31     if (a == 0) ax = 0;
 32     if (b == 0) bx = 0;
 33     if (b == 2) {
 34         ed = d;tip = 1;half = 0;sum = k;
 35         return;
 36     }
 37     if (a == 2){
 38         ed = d;
 39 //        cout << a*ax+b*bx-k<<endl;
 40 //    cout << a <<' '<<ax<<' '<<b<<' '<<bx<<' '<<k<<endl;
 41         if (k <= bx) {sum = k;half = b/2;}
 42         else {sum = k-bx;half = 0;tip = 2;}
 43         return;
 44     }
 45     if (ax + bx >= k){
 46         ed = d;
 47 //        cout<<a<<' '<<ax<<' '<<b<<' '<<bx<<' '<<k<<endl;
 48         if (b&1) {
 49             if (k <= bx) sum = k,half = b/2;
 50             else sum = k-bx,half = b/2-1;
 51         }
 52         else {
 53             sum = k,half = b/2-1;
 54         }
 55         return;
 56     }
 57     k -= ax+bx;
 58     if (a == 0){
 59         if (b&1) solve(0,0,b/2,bx+bx,k,d+1);
 60         else solve(b/2-1,bx,b/2,bx,k,d+1);
 61     }
 62     else{
 63         if (a&1) solve(a/2,ax+ax+bx,a/2+1,bx,k,d+1);
 64         else solve(a/2-1,ax,b/2,ax+bx+bx,k,d+1);
 65     }
 66 }
 67 void getans(ll p,int d){
 68     if (d == ed) {
 69         if (tip){
 70             if (p <= 2) ans += sum;
 71             else if (sum == 1) ans++;
 72             else if (sum == 2) ans +=3;
 73         }
 74         else{
 75             if (p <= 2) ans += sum;
 76             else ans += (p+1)/2;
 77         }
 78         return;
 79     }
 80     if (p&1){
 81         if (check(p/2,d+1)) getans(p/2,d+1);
 82         else {ans += p/2+1;getans(p/2,d+1);}
 83     }
 84     else{
 85         if (check(p/2-1,d+1)) getans(p/2-1,d+1);
 86         else {ans += p/2;getans(p/2,d+1);}
 87     }
 88 }
 89 bool check(ll p,int d){
 90     if (p == 0) return 0;
 91     ll w = getsum(0,0,p,1,d);
 92 //    cout << w <<' '<<sum<<endl;
 93     if (w >= sum) return 1;
 94     else {sum -= w;return 0;}
 95 //    return getsum(0,0,p,1,d) >= sum;
 96 }
 97 ll getsum(ll a,ll ax,ll b,ll bx,int d){
 98     if (a == 0) ax = 0;
 99     if (b == 0) bx = 0;
100     if (d == ed){
101         if (tip){
102 //            cout << a << ' ' << b <<' '<<bx<< endl;
103             ll ans = 0;
104             if (a <= 2) ans += a*ax;
105             if (b <= 2) ans += b*bx;
106             else if (b == 3) ans += bx*2; 
107             return ans;
108         }
109         ll ans = 0;
110         if ((b-1)/2 == half) ans += bx;
111         if ((a-1)/2 == half) ans += ax;    
112         return ans;
113     }
114     if (a == 0){
115         if (b&1) return getsum(0,0,b/2,bx+bx,d+1);
116         else return getsum(b/2-1,bx,b/2,bx,d+1);
117     }
118     else{
119         if (a&1) getsum(a/2,ax+ax+bx,a/2+1,bx,d+1);
120         else return getsum(a/2-1,ax,b/2,ax+bx+bx,d+1);
121     }    
122 }