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 }
标签：2023.08,node,ch,20CCPC,int,网络,dfs,yy,xx From： https://www.cnblogs.com/burutaofan/p/17659706.html