2023.08.20CCPC网络赛
rank：732，寄
首先开场打E手速不行，还WA了一两发，其次D开始觉得是二分让队友先写了一发，后面看出是三分，但是反应过来的时候只剩20min了，而且是在队友之前的代码上改的，手忙脚乱，最后还是没有调出来，令人寒心；
D.Discrete Fourier Transform
题意：根据欧拉公式可以将原式化成许多个与 fk 的值为变量的二次函数，要使得这些二次函数的最大值最小，我们不妨取一个新函数 g ( x ) = max { fi ( x ) }，1<=N，其中 fi ( x ) 是原本的第i个函数的值，再用三分的方法求该函数的最小值；
暂时还没有找到在哪里交题，先把赛后重新写的代码（不保真）贴在这里；
1 #include<bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 ll read(){ 5 char ch=getchar();ll x=0,f=1; 6 while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} 7 while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} 8 return x*f; 9 } 10 const int maxn=2005; 11 const double pi=acos(-1); 12 ll N,K; 13 ll f[maxn]; 14 struct node{ 15 double A,B; 16 double a,b,c; 17 }F[maxn]; 18 double work(ll x){ 19 double ret=-1e18; 20 for(int i=0;i<=N-1;i++){ 21 double now=F[i].a*x*x+F[i].b*x+F[i].c; 22 ret=max(ret,now); 23 } 24 return ret; 25 } 26 int main(){ 27 N=read();K=read(); 28 for(int i=0;i<=N-1;i++){ 29 f[i]=read(); 30 } 31 for(int i=0;i<=N-1;i++){ 32 for(int j=0;j<=N-1;j++){ 33 if(j==K)continue; 34 F[i].A+=f[j]*cos(2.0*pi*i*j/N); 35 F[i].B+=f[j]*sin(2.0*pi*i*j/N); 36 } 37 F[i].a=1; 38 F[i].b=2*(F[i].A*cos(2.0*pi*i*K/N)+F[i].B*sin(2.0*pi*i*K/N)); 39 F[i].c=F[i].A*F[i].A+F[i].B*F[i].B; 40 } 41 ll L=-1e18,R=1e18; 42 while(R-L>=3){ 43 ll midl=L+(R-L)/3; 44 ll midr=R-(R-L)/3; 45 if(work(midl)<=work(midr))R=midr; 46 else L=midl; 47 } 48 double ans=1e18; 49 for(ll i=L;i<=R;i++){ 50 ans=min(ans,work(i)); 51 } 52 cout<<fixed<<setprecision(10)<<sqrt(ans)<<endl; 53 return 0; 54 }
E.Robot Experiment
题意：给定你机器人的路径，如果下一步到达的位置有障碍则停在原地，起点（0，0）一定无障碍，记录所有可能最后停留的位置并按字典序输出；
深搜即可，注意已经到达过的位置一定不会有障碍，且去重；
赛后补的代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 int read(){ 4 char ch=getchar();int x=0,f=1; 5 while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} 6 while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} 7 return x*f; 8 } 9 const int maxn=205; 10 int N,tot,A[25]; 11 int dx[10]={-1,1,0,0}; 12 int dy[10]={0,0,-1,1}; 13 map<pair<int,int>,int>vis; 14 map<pair<int,int>,int>b; 15 map<pair<int,int>,int>ans; 16 struct node{ 17 int x,y; 18 }e[maxn]; 19 int cmp(node a,node b){ 20 if(a.x==b.x)return a.y<b.y; 21 return a.x<b.x; 22 } 23 void dfs(int x,int y,int k){ 24 if(k==N+1){ 25 if(ans[make_pair(x,y)]==0){ 26 tot++; 27 e[tot].x=x;e[tot].y=y; 28 ans[make_pair(x,y)]=1; 29 } 30 return ; 31 } 32 b[make_pair(x,y)]++; 33 int xx=x+dx[A[k]],yy=y+dy[A[k]]; 34 if(vis[make_pair(xx,yy)]==0){ 35 if(b[make_pair(xx,yy)]==0){ 36 vis[make_pair(xx,yy)]=1; 37 dfs(x,y,k+1); 38 vis[make_pair(xx,yy)]=0; 39 } 40 dfs(xx,yy,k+1); 41 } 42 else dfs(x,y,k+1); 43 b[make_pair(x,y)]--;//注意，开始写的是经过时变成1退出时变成0，会错，因为可能多次经过 44 } 45 int main(){ 46 N=read(); 47 for(int i=1;i<=N;i++){ 48 char ch; 49 cin>>ch; 50 if (ch=='L') A[i]=0; 51 if (ch=='R') A[i]=1; 52 if (ch=='D') A[i]=2; 53 if (ch=='U') A[i]=3; 54 } 55 dfs(0,0,1); 56 cout<<tot<<endl; 57 sort(e+1,e+tot+1,cmp); 58 for(int i=1;i<=tot;i++){ 59 cout<<e[i].x<<" "<<e[i].y<<endl; 60 } 61 return 0; 62 }
赛时和队友一起写的代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 struct node{ 4 int x,y; 5 bool operator <(const node &a) const{ 6 if (a.x == x) 7 return y < a.y; 8 return x < a.x; 9 } 10 }; 11 const int d = 100; 12 int N,tot,A[25]; 13 int vis[200][200],b[200][200]; 14 int dx[10]={-1,1,0,0}, dy[10]={0,0,-1,1}; 15 set<node> ans; 16 void dfs(int x,int y,int k){ 17 if (k == N+1){ 18 x -= d, y -= d; 19 if (!ans.count((node){x,y})){ 20 tot ++; 21 ans.insert((node){x,y}); 22 } 23 return ; 24 } 25 b[x][y] ++; 26 int xx = x + dx[A[k]], yy = y + dy[A[k]]; 27 if (vis[xx][yy] == 0){ 28 if (b[xx][yy] == 0){ 29 vis[xx][yy] = 1; 30 dfs(x, y, k+1); 31 vis[xx][yy] = 0; 32 } 33 dfs(xx, yy, k+1); 34 } 35 else 36 dfs(x, y, k+1); 37 b[x][y] --; 38 } 39 int main(){ 40 cin>>N; 41 for(int i=1;i<=N;i++){ 42 char ch; 43 cin >> ch; 44 if (ch=='L') A[i]=0; 45 if (ch=='R') A[i]=1; 46 if (ch=='D') A[i]=2; 47 if (ch=='U') A[i]=3; 48 } 49 dfs(d,d,1); 50 cout << tot << endl; 51 for (auto it: ans) 52 cout << it.x << ' ' << it.y << endl; 53 return 0; 54 }