比赛地址
Pro: 8/8/13
Rank: 19/112
[A] Accurate Movement
题意&题解
签到题
代码
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int a, b, n;
int main() {
cin >> a >> b >> n;
int tim = 0, nowb = b;
while(nowb < n) { tim++; nowb += b-a; }
printf("%d\n", tim*2+1);
return 0;
}
[B] Bad Treap
题意
给出一个Treap的创建规则,其权值y和键值x的关系是y=\sin x.求一组数据,把这种方法构造的Treap卡成一条链.
题解
很有意思的数学题.
大致思路是,找到一个初值k,要保证k这个位置的导数是小于0的.然后找一个稍微比2\pi或者其倍数大一点点的数T作为周期,然后把k+xT作为构造出的序列.这样,每经过一个周期,函数值都会比之前稍微小一点点,就构造出了需要的序列.
然后就是暴力打表找符合要求的数了.下面选的710这个数就非常接近2\pi的113倍.
代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
using namespace std;
int main() {
int k = -710*25000; int n;
cin >> n;
for (int i = 1; i <= n; i++) {
k += 710;
printf("%d\n", k);
}
return 0;
}
[E] Equidistant
题意
给出一棵树,然后在上面钦定一些点,求能否在树上找到一个点,使得这个点到那些被钦定的点的距离都相等.
题解
结论题.找到距离最远的一对被钦定的点,然后找它们的中点.如果没有中点就不存在,否则答案只可能是这个中点,再BFS一遍检查下是否符合题意就行了.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL long long
#define N 400010
#define INF 0x3f3f3f3f
using namespace std;
int n,i,m,x,y,root,Ans,top,lsum=1;
int head[N],v[N],d[N],f[N];
struct Edge{
int t,next;
}e[N*8];
inline void Add(int s,int t){
e[lsum].t=t; e[lsum].next=head[s]; head[s]=lsum++;
}
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
IL void Dfs(int x,int fa){
reg int i=0;
for (i=head[x];i;i=e[i].next){
if (e[i].t==fa) continue;
f[e[i].t]=x; d[e[i].t]=d[x]+1;
if (v[e[i].t] && d[e[i].t]>d[0]){
d[0]=d[e[i].t];
top=e[i].t;
}
Dfs(e[i].t,x);
}
}
IL void Check(int x,int fa){
reg int i=0;
if (v[x]){
if (root==-1) root=d[x];
else {
if (root!=d[x]) top=1;
}
}
for (i=head[x];i;i=e[i].next){
if (e[i].t==fa) continue;
d[e[i].t]=d[x]+1;
Check(e[i].t,x);
}
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
n=read(); m=read();
for (i=1;i<n;i++){
x=read(); y=read();
Add(x,y); Add(y,x);
}
if (m==1){
cout<<"YES"<<endl;
cout<<"1"<<endl;
return 0;
}
for (i=1;i<=m;i++){
x=read(); v[x]=1; root=x;
}
Dfs(root,0); root=top;
memset(d,0,sizeof(d));
memset(f,0,sizeof(f));
Dfs(root,0);
if (d[top]%2){
cout<<"NO"<<endl;
return 0;
}
x=top; y=d[top]/2;
while (d[x]!=y) x=f[x];
Ans=x; top=0; root=-1;
memset(d,0,sizeof(d));
Check(Ans,0);
if (top) cout<<"NO"<<endl;
else {
cout<<"YES"<<endl;
cout<<x<<endl;
}
return 0;
}
[H] High Load Database
题意
给出一个长度为n的序列a_{i},然后有q组询问,每一组询问会给出一个t,问能否把原序列分成尽可能小的段数,使得每一小段序列的总和不超过t.
题解
对于单个询问,需要贪心算最小的段数.问题是如何求大量的询问.
正解是记忆化+二分答案,通过预处理前缀和,然后每一次通过二分来枚举当前分段的长度,单次询问的复杂度是\frac{n}{t}\log n的.因为加了记忆化,所以可以认为t是在不断递增的,然后根据调和级数求和就可以知道最后的复杂度是O(n \log n \log n).
我的解法没有用到二分,直接预处理从每个位置开始,向后跳到哪个位置可以使分段的和刚好不超过2^{i}.然后对于每个询问,借助这个预处理来进行跳转.中间同样使用了记忆化来处理.时间复杂度理论上是和上面的一样的,实际感觉常数会稍微大一些.
代码
#pragma GCC optimize(3)
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL long long
#define N 200010
#define INF 0x3f3f3f3f
using namespace std;
int n,i,x,m,q,y;
int a[N],p[50];
LL s[N];
int f[N][22];
map <int,int> M;
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
IL void Ready(){
reg int i=0,j=0,x=0,y=0;
for (i=1;i<=n;i++) s[i]=s[i-1]+a[i];
for (i=1;i<=n;i++) m=Max(m,a[i]);
for (i=1;i<=1000000;i<<=1){
for (j=1;j<=n;j++){
y=Max(f[j-1][x],j);
if (a[j]>i){
f[j][x]=-1;
continue;
}
while (y<n && s[y+1]-s[j-1]<=i) y++;
f[j][x]=y;
}
x++;
}
p[0]=1;
for (i=1;i<=19;i++) p[i]=p[i-1]<<1;
/* for (i=0;i<=5;i++)
for (j=1;j<=n;j++)
cout<<p[i]<<" "<<" "<<j<<" "<<f[j][i]<<endl;*/
}
IL int Work(int x){
reg int i=0,j=0,k=0,ans=0,y=0;
y=x;
for (i=1;i<=n;){
if (y<a[i]) {
ans++; y=x; continue;
}
for (j=19;j>=0;j--){
if (y<p[j]) continue;
if (f[i][j]==-1) continue;
y-=s[f[i][j]]-s[i-1]; i=f[i][j]+1;
break;
}
if (i>n) break;
if (y>=a[i]) {
y-=a[i]; i++; continue;
}
}
if (y<x) ans++;
return ans;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
n=read();
for (i=1;i<=n;i++) a[i]=read();
Ready();
q=read();
for (i=0;i<=200;i++)
M[m+i]=Work(m+i);
while (q--){
x=read();
if (x<m){
puts("Impossible");
continue;
}
if (M[x]) printf("%d\n",M[x]);
else {
y=Work(x); M[x]=y;
printf("%d\n",y);
}
}
return 0;
}
[I] Ideal Pyramid
题意
给出空间中的n个点,然后要求构造一个尽可能小的四棱锥,使得这个四棱锥可以包住所有的点.要求四棱锥底面的边和坐标轴平行,而且侧面和底面成45度角.
题解
投影到侧面上之后直接处理,然后合并答案.
代码
#include <cstdio>
#include <algorithm>
#include <climits>
using namespace std;
#define LL long long
LL x[1234], y[1234], h[1234];
int main()
{
LL minx = INT_MAX, miny = INT_MAX, maxx = INT_MIN, maxy = INT_MIN;
int n;
scanf("%d", &n);
for (int i=1; i<=n; i++)
{
scanf("%lld %lld %lld", &x[i], &y[i], &h[i]);
minx = min(minx, x[i] - h[i]);
maxx = max(maxx, x[i] + h[i]);
miny = min(miny, y[i] - h[i]);
maxy = max(maxy, y[i] + h[i]);
}
LL xx = (minx + maxx) / 2;
LL yy = (miny + maxy) / 2;
printf("%lld %lld %lld\n", (minx + maxx) / 2, (miny + maxy) / 2, max(
max(xx - minx, yy - miny),
max(maxx - xx, maxy - yy)
));
}
[J] Just the Last Digit
题意
给出一个拓扑图,保证每条有向边都是从小编号连向大编号.现在这个图的连边情况未知,只知道任意两点间的路径数目对10取模的结果,求原图的连边情况.
题解
先不考虑取模,从小到大枚举i,然后从i-1到1倒序枚举j,计算j到i之前是否有直接连边.通过枚举中间节点k,然后检测j是否能直接到k,如果可以,就把总的方案数减去k到i的方案数.最后剩下的方案数如果是0说明没有连边,1说明有.
然后把上面的过程放到模10意义下进行.不难发现,最后的结果对10取模一定还是0或1,所以还是可以通过上面的方法直接判断.注意负数对10取模的结果可能还是负数,需要再取一次模转成正的.
代码
#pragma GCC optimize(3)
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL long long
#define N 510
#define INF 0x3f3f3f3f
using namespace std;
int n,i,j,k,x;
char c[N];
int a[N][N],b[N][N];
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
scanf("%d",&n);
for (i=1;i<=n;i++){
scanf("%s",&c);
for (j=0;j<n;j++)
a[i][j+1]=c[j]-48;
}
for (i=2;i<=n;i++)
for (j=i-1;j;j--){
x=a[j][i];
for (k=j+1;k<i;k++)
(b[k][i])?x-=a[j][k]:0;
x=(x+10)%10;
x=(x+10)%10;
b[j][i]=(x==1);
}
for (i=1;i<=n;i++){
for (j=1;j<=n;j++)
putchar(b[i][j]+48);
putchar(10);
}
return 0;
}
[K] King’s Children
题意
给出一个矩形,这个矩形中有一些位置分布着一个大写字母.要求把这个矩形分成若干个小矩形,每个小矩形恰好包含一个大写字母,而且包含A字母的矩形的面积尽可能地大.
题解
先通过悬线法找到包含A的最大矩形,接着对剩下的位置分隔就行了.
代码
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int n, m, ax, ay;
char s[2005];
int h[1005][1005], l[1005][1005], r[1005][1005];
int map[1005][1005], a[1005][1005], ans[1005][1005];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%s", s);
int lenj = strlen(s);
for (int j = 1; j <= lenj; j++) {
if (s[j-1] == '.') map[i][j] = 0;
else if (s[j-1] == 'A') { ax = i, ay = j; map[i][j] = 0; }
else map[i][j] = s[j-1] - 'A';
}
}
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) a[i][j] = (map[i][j] == 0);
for (int i = 1; i <= n; i++) a[i][0] = a[i][m+1] = 1;
for (int j = 1; j <= m; j++) a[0][j] = a[n+1][j] = 1;
//for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= m; j++) printf("%d", a[i][j]);
// cout << endl;
//}
int i, j, up, down, left, right, maxans = 0;
for (i=1;i<=m;i++) h[1][i]=1;
for (i=1;i<=n;i++){
r[i][m]=l[i][1]=0;
for (j=2;j<=m;j++) l[i][j]=(l[i][j-1]+1)*((a[i][j]+a[i][j-1]==2));
for (j=m-1;j;j--) r[i][j]=(r[i][j+1]+1)*((a[i][j]+a[i][j+1]==2));
}
for (i=2;i<=n;i++) for (j=1;j<=m;j++)
if (a[i][j]+a[i-1][j]==2){
l[i][j]=min(l[i][j],l[i-1][j]);
r[i][j]=min(r[i][j],r[i-1][j]);
h[i][j]=h[i-1][j]+1;
} else h[i][j]=1;
//printf("%d %d\n", ax, ay);
for (i=1;i<=n;i++) for (j=1;j<=m;j++) {
if (i < ax) continue;
if (i - ax + 1 > h[i][j]) continue;
if (ay < j-l[i][j]) continue;
if (ay > j+r[i][j]) continue;
if (h[i][j]*(l[i][j]+r[i][j]+1) > maxans) {
maxans = h[i][j]*(l[i][j]+r[i][j]+1);
up = i - h[i][j];
down = i+1;
left = j - l[i][j] - 1;
right = j + r[i][j] + 1;
}
}
for (int i = up+1; i < down; i++) for (int j = left+1; j < right; j++) ans[i][j] = 'a';
ans[ax][ay] = 'A';
int last;
for (int j = left; j >= 1; j--) {
last = up+1;
for (int i = up+1; i < down; i++) if (map[i][j]) {
for (int k = last; k <= i; k++) ans[k][j] = map[i][j] + 'a';
last = i + 1;
}
if (last == up+1) for (int i = up+1; i < down; i++) ans[i][j] = ans[i][j+1];
else for (int i = last; i < down; i++) ans[i][j] = ans[i-1][j];
}
for (int j = right; j <= m; j++){
last = up+1;
for (int i = up+1; i < down; i++) if (map[i][j]) {
for (int k = last; k <= i; k++) ans[k][j] = map[i][j] + 'a';
last = i + 1;
}
if (last == up+1) for (int i = up+1; i < down; i++) ans[i][j] = ans[i][j-1];
else for (int i = last; i < down; i++) ans[i][j] = ans[i-1][j];
}
for (int i = up; i >= 1; i--) {
last = 1;
for (int j = 1; j <= m; j++) if (map[i][j]) {
for (int k = last; k <= j; k++) ans[i][k] = map[i][j] + 'a';
last = j + 1;
}
if (last == 1) for (int j = 1; j <= m; j++) ans[i][j] = ans[i+1][j];
else for (int j = last; j <= m; j++) ans[i][j] = ans[i][j-1];
}
for (int i = down; i <= n; i++) {
last = 1;
for (int j = 1; j <= m; j++) if (map[i][j]) {
for (int k = last; k <= j; k++) ans[i][k] = map[i][j] + 'a';
last = j + 1;
}
if (last == 1) for (int j = 1; j <= m; j++) ans[i][j] = ans[i-1][j];
else for (int j = last; j <= m; j++) ans[i][j] = ans[i][j-1];
}
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++)
if (map[i][j]) ans[i][j] = map[i][j] + 'A';
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) printf("%c", ans[i][j]);
cout << endl;
}
return 0;
}
[M] Lengths and Periods
题意&题解
签到题
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<unordered_map>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL long long
#define N 2020
#define INF 0x3f3f3f3f
using namespace std;
int T,n,i,j,x,cnt;
LL ans;
int a[N];
int s[N][N];
unordered_map <int,int> M;
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
T=read();
while (T--){
n=read(); ans=0; M.clear(); cnt=0;
for (i=1;i<=n;i++) a[i]=read();
memset(s,0,sizeof(s));
for (i=1;i<=n;i++){
if (!M.count(a[i])) {
M[a[i]]=++cnt;
}
s[i][M[a[i]]]=1;
}
for (i=1;i<=cnt;i++)
for (j=1;j<=n;j++)
s[j][i]+=s[j-1][i];
for (i=1;i<=n;i++)
for (j=i+1;j<=n;j++){
x=a[j]+(a[j]-a[i]);
if (!M.count(x)) continue;
x=M[x];
ans+=(LL)(s[n][x]-s[j][x]);
}
printf("%lld\n",ans);
}
return 0;
}
总结
毛子的题目质量还是非常可以的,比如B题出的就很有数学水平.整场的发挥还可以,中期稍有卡顿,但是后期比之前的几次好很多.从罚时上来开还有一些提升空间,比如作为中档题中的签到题的J题应该在更早之前就做出来,K题在给队友用悬线法板子的时候,中间在沟通上出了一些偏差,导致板子使用错误卡了一会.感觉要是可以面对面交流的话应该不会出现这样的情况.
比赛中间的失误还是有的,例如一开始认为J题对10取模后不可做,过了很长时间反应过来才重新提交.H题被经验带歪了,一直认为要通过数据结构维护一些信息来降时间复杂度,这种记忆化询问的方式还是很少见的.
声明:
本文采用
BY-NC-SA
协议进行授权，如无注明均为原创，转载请注明转自
Marvolo
本文地址: 2019ICPC North-Western Russia Regional Contest部分题解
本文地址: 2019ICPC North-Western Russia Regional Contest部分题解
