Result：191/1371
AC：5/12
Dir：
xf从后往前开，yh从前往后开，我从中间乱开（），第一个随便看了个G(lol那题)，感觉没有k的限制是个水题，有k的限制想了5分钟妹想出来，换了个C，发现数据范围为1-4，就手玩了几组数据，发现和nm奇偶性有关，和yh说了一下感觉能过，但特判的n=1m=1忘删除了，导致上来就WA了一发，之后感觉正确性我没证明白，删掉特判之后也没敢继续交，大概20min，yh切了个D，他怂恿我冲一下，交了C过了，之后去开F，很明显是个阿波罗尼斯⚪，滚去一边推到两个球的球心和半径，推的差不多了拿电脑开始写，写完了样例过了，交上去又WA一发，（已经开始慌了），队友把K想出来上去之后把K过了，我把xf叫来当小黄鸭推到几何那题过程，发现有个公式打错了，改了一下交上去又WA一发，已经开始懵逼了，之后队友去开I，我接着肉眼看K，发现一个kk打成了k，改完之后 K过了，之后和队友debug I ，感觉没什么问题，但就是改不过来，就先扔了，我去开 H，队友去开J，队友交了一发J，t了，我感觉H写出来了递推，然后上去写完WA了一发，xf随便口胡了组数据把我hack掉了（），还剩最后30min,我已经开始摸鱼了，突然yh大叫一声：“你数学爷爷来啦！ ”，I的锅在输出，改完在最后时刻A了，5题结束，总而言之比较体面，但谔谔错误也比较多，之后需要继续改进（）。
比赛结束之后看题解，发现我们写的五个题确实是最简单的五个，开题顺序似乎海星（）。害真就背刺沃尔沃夫了
下面是题解（持续更新）：
A
传送门
思路：题害没看
代码：妹写
B
传送门
思路：看了但没完全看懂
代码：妹写
C
传送门
思路：最终的结果是走n*m-1步，确定奇偶性即可
代码：签到题
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
int n,m;
int main(){
scanf("%d%d",&n,&m);
int k=n*m;
if(k&1) printf("NO");
else printf("YES");
return 0;
}
D
传送门
思路：yh写的，听说是个水题
代码：也是yh写的，我先放这儿了，等我写完再贴我的
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<deque>
#define ll long long int
using namespace std;
int value(int a, int b){
if(a>b) {
int temp = a;
a = b;
b = temp;
}
if(a==2&&b==8) return 1000;
if(a==b){
return 900+a;
}
else{
return 800+((a+b)%10);
}
}
char* solve(){
int a[2], b[2];
scanf("%d%d%d%d",a,b,a+1,b+1);
if(a[0]>b[0]) {
int temp = a[0];
a[0] = b[0];
b[0] = temp;
}
if(a[1]>b[1]) {
int temp = a[1];
a[1] = b[1];
b[1] = temp;
}
if(a[0]!=b[0]&&a[1]!=b[1]&&(a[0]+b[0])%10==(a[1]+b[1])%10){
if(b[0]>b[1]) return "first";
else if(b[0]<b[1]) return "second";
else return "tie";
}
int f1 = value(a[0],b[0]), f2 = value(a[1],b[1]);
if(f1>f2) return "first";
else if(f1<f2) return "second";
else return "tie";
}
int main(){
int t;
scanf("%d",&t);
while(t--) printf("%s\n",solve());
}
F
传送门
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
int t;
const double pi = acos(-1);
double k,kk;
struct NODE{
double x,y,z;
double r;
}point[15],p1,p2;
double dis(NODE p, NODE q) {
double ans=sqrt((p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y)+(p.z-q.z)*(p.z-q.z));
return ans;
}
inline void prework(){
p1.x=(-1)*((point[1].x-k*k*point[2].x)/(k*k-1));
p1.y=(-1)*((point[1].y-k*k*point[2].y)/(k*k-1));
p1.z=(-1)*((point[1].z-k*k*point[2].z)/(k*k-1));
double xx=((point[1].x-k*k*point[2].x)/(k*k-1))*((point[1].x-k*k*point[2].x)/(k*k-1));
double yy=((point[1].y-k*k*point[2].y)/(k*k-1))*((point[1].y-k*k*point[2].y)/(k*k-1));
double zz=((point[1].z-k*k*point[2].z)/(k*k-1))*((point[1].z-k*k*point[2].z)/(k*k-1));
p1.r=sqrt((k*k*(point[2].x*point[2].x+point[2].y*point[2].y+point[2].z*point[2].z)-(point[1].x*point[1].x+point[1].y*point[1].y+point[1].z*point[1].z))/(1-k*k)+(xx+yy+zz));
p2.x=(-1)*((point[3].x-kk*kk*point[4].x)/(kk*kk-1));
p2.y=(-1)*((point[3].y-kk*kk*point[4].y)/(kk*kk-1));
p2.z=(-1)*((point[3].z-kk*kk*point[4].z)/(kk*kk-1));
double xxx=((point[3].x-kk*kk*point[4].x)/(kk*kk-1))*((point[3].x-kk*kk*point[4].x)/(kk*kk-1));
double yyy=((point[3].y-kk*kk*point[4].y)/(kk*kk-1))*((point[3].y-kk*kk*point[4].y)/(kk*kk-1));
double zzz=((point[3].z-kk*kk*point[4].z)/(kk*kk-1))*((point[3].z-kk*kk*point[4].z)/(kk*kk-1));
p2.r=sqrt((kk*kk*(point[4].x*point[4].x+point[4].y*point[4].y+point[4].z*point[4].z)-(point[3].x*point[3].x+point[3].y*point[3].y+point[3].z*point[3].z))/(1-kk*kk)+(xxx+yyy+zzz));
}
inline void cal(){
double ans=0;
double dd=dis(p1,p2);
if (dd>=p1.r+p2.r){
printf("%.6lf\n",ans);
return ;
}
else if(dd+p1.r<=p2.r) {
ans=(4.0/3)*pi*p1.r*p1.r*p1.r;
printf("%.6lf\n",ans);
return ;
}
else if(dd+p2.r<=p1.r){
ans=(4.0/3)*pi*p2.r*p2.r*p2.r;
printf("%.6lf\n",ans);
return ;
}
else{
double co=(p2.r*p2.r+dd*dd-p1.r*p1.r)/(2.0*dd*p2.r);
double h=p2.r*(1-co);
ans+=(1.0/3)*pi*(3.0*p2.r-h)*h*h;
co=(p1.r*p1.r+dd*dd-p2.r*p2.r)/(2.0*dd*p1.r);
h=p1.r*(1-co);
ans+=(1.0/3)*pi*(3.0*p1.r-h)*h*h;
printf("%.6lf\n",ans);
return ;
}
}
int main(){
scanf("%d",&t);
while(t--){
for(int i=1;i<=4;i++) scanf("%lf%lf%lf",&point[i].x,&point[i].y,&point[i].z);
scanf("%lf%lf",&k,&kk);
prework();
cal();
}
return 0;
}
I
传送门
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#define ll long long int
using namespace std;
char p1[22][22];
char p2[22][22];
typedef struct _copoint{
int x1, y1, x2, y2;
_copoint(int x1, int y1, int x2, int y2):x1(x1),y1(y1),x2(x2),y2(y2){ }
bool operator==(const _copoint& other){
return x1==other.x1&&y1==other.y1&&x2==other.x2&&y2==other.y2;
}
struct _copoint L(){
struct _copoint co = _copoint(x1,y1,x2,y2);
if(y1>0&&p1[x1][y1-1]!='#') co.y1--;
if(y2>0&&p2[x2][y2-1]!='#') co.y2--;
return co;
}
struct _copoint U(){
struct _copoint co = _copoint(x1,y1,x2,y2);
if(x1>0&&p1[x1-1][y1]!='#') co.x1--;
if(x2>0&&p2[x2-1][y2]!='#') co.x2--;
return co;
}
struct _copoint R(){
struct _copoint co = _copoint(x1,y1,x2,y2);
if(y1<19&&p1[x1][y1+1]!='#') co.y1++;
if(y2<19&&p2[x2][y2+1]!='#') co.y2++;
return co;
}
struct _copoint D(){
struct _copoint co = _copoint(x1,y1,x2,y2);
if(x1<19&&p1[x1+1][y1]!='#') co.x1++;
if(x2<19&&p2[x2+1][y2]!='#') co.x2++;
return co;
}
struct _copoint Step(char c){
switch(c){
case 'L': return L();
case 'U': return U();
case 'R': return R();
case 'D': return D();
}
}
} Copoint;
#define coarr(_arr, _pos) _arr[_pos.x1][_pos.y1][_pos.x2][_pos.y2]
queue<Copoint> q;
int len[22][22][22][22];
int jdg[22][22][22][22];
char rout[22][22][22][22][420];
int main(){
for(int i=0;i<20;i++) {
scanf("%s %s",p1[i],p2[i]);
for(int j=0;j<10;j++){
char t = p1[i][j];
p1[i][j] = p1[i][19-j];
p1[i][19-j] = t;
}
}
// printf("\n\n\n%c\n\n\n\n",p2[19][19]);
q.push(Copoint(19,0,19,0));
jdg[19][0][19][0] = 1;
while(true){
Copoint src = q.front();
// printf("SIZE:%d SRC: %d %d %d %d ROUT: %s\n",q.size(),src.x1,src.y1,src.x2,src.y2,coarr(rout,src));
if(src==Copoint(0,0,0,0)){
break;
}
q.pop();
Copoint nxt(0,0,0,0);
nxt = src.D();
if(!coarr(jdg, nxt)){
// printf("NEXT %d %d %d %d\n",nxt.x1,nxt.y1,nxt.x2,nxt.y2);
coarr(jdg, nxt) = 1;
coarr(len, nxt) = coarr(len, src) + 1;
strcpy(coarr(rout, nxt), coarr(rout, src));
coarr(rout, nxt)[coarr(len, nxt)-1] = 'D';
q.push(nxt);
}
nxt = src.R();
if(!coarr(jdg, nxt)){
// printf("NEXT %d %d %d %d\n",nxt.x1,nxt.y1,nxt.x2,nxt.y2);
coarr(jdg, nxt) = 1;
coarr(len, nxt) = coarr(len, src) + 1;
strcpy(coarr(rout, nxt), coarr(rout, src));
coarr(rout, nxt)[coarr(len, nxt)-1] = 'R';
q.push(nxt);
}
nxt = src.L();
if(!coarr(jdg, nxt)){
// printf("NEXT %d %d %d %d\n",nxt.x1,nxt.y1,nxt.x2,nxt.y2);
coarr(jdg, nxt) = 1;
coarr(len, nxt) = coarr(len, src) + 1;
strcpy(coarr(rout, nxt), coarr(rout, src));
coarr(rout, nxt)[coarr(len, nxt)-1] = 'L';
q.push(nxt);
}
nxt = src.U();
if(!coarr(jdg, nxt)){
// printf("NEXT %d %d %d %d\n",nxt.x1,nxt.y1,nxt.x2,nxt.y2);
coarr(jdg, nxt) = 1;
coarr(len, nxt) = coarr(len, src) + 1;
strcpy(coarr(rout, nxt), coarr(rout, src));
coarr(rout, nxt)[coarr(len, nxt)-1] = 'U';
q.push(nxt);
}
}
Copoint p = Copoint(19,0,19,0);
p1[19][0] = 'A';
p2[19][0] = 'A';
for(int i=0;i<len[0][0][0][0];i++){
p = p.Step(rout[0][0][0][0][i]);
p1[p.x1][p.y1] = 'A';
p2[p.x2][p.y2] = 'A';
if(rout[0][0][0][0][i]=='L') rout[0][0][0][0][i]='R';
else if(rout[0][0][0][0][i]=='R') rout[0][0][0][0][i]='L';
}
printf("%d\n%s\n",len[0][0][0][0],rout[0][0][0][0]);
for(int i=0;i<20;i++) {
for(int j=0;j<10;j++){
char t = p1[i][j];
p1[i][j] = p1[i][19-j];
p1[i][19-j] = t;
}
}
for(int i=0;i<20;i++) {
printf("%s %s",p1[i],p2[i]);
if(i<19) printf("\n");
}
return 0;
}
K
传送门
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<deque>
#define ll long long int
using namespace std;
typedef struct{
int p;
int x;
} Pair;
int cmp(const void* p1, const void* p2){
return ((Pair*)p1)->p - ((Pair*)p2)->p;
}
#define MAX 2000000
Pair p[MAX];
int _next[MAX];
int pop[MAX];
vector<int> instackpos; // root = 0
int a[MAX];
int main(){
int n, k;
scanf("%d %d",&n,&k);
for(int i=0;i<k;i++)scanf("%d%d",&p[i].p,&p[i].x);
qsort(p,k,sizeof(Pair),cmp);
Pair last;
last.p = 0;
last.x = 0;
for(int i=0;i<k;i++){
int dp = p[i].p - last.p;
int dx = p[i].x - last.x;
if(dp<dx){
printf("-1");
return 0;
}
pop[p[i].p] = dp-dx;
last = p[i];
}
//for(int i=1;i<=n;i++)printf("pop[%d]=%d\n",i,pop[i]);
instackpos.push_back(0);
for(int i=1;i<=n;i++){
int linkpos = instackpos.size() - 1 - pop[i];
_next[i] = _next[instackpos[linkpos]];
_next[instackpos[linkpos]] = i;
for(int j=0;j<pop[i];j++) instackpos.pop_back();
instackpos.push_back(i);
}
//for(int i=0;i<=n;i++)printf("_next[%d]=%d\n",i,_next[i]);
int lastpos = 0;
for(int i=1;i<=n;i++){
lastpos = _next[lastpos];
a[lastpos] = i;
}
for(int i=1;i<=n;i++)printf("%d ",a[i]);
printf("\n");
}
/*
10 7
1 1
2 1
5 1
6 1
7 1
8 1
10 1
5 3
1 1
2 1
5 1
*/