E - Laser Takahashi
我真的服了，e题卡我精度。第一次提交wa23个，加了eps，wa17个，改用f128，结果wa7个。不是哥们，明明做法都是一样的凭什么我的精度会挂掉。真的服了。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N(2e5+5);
int n,q;
int cnt[N],id[N],pre[N]; //cnt:每方向怪物数 id:怪物方向编号 pre:前缀和
map<pair<int,int>,vector<int>>mp; //方向->怪物列表
vector<pair<int,int>>dir; //全部方向向量
bool cmp(pair<int,int>a,pair<int,int>b){auto[x1,y1](a);auto[x2,y2](b);bool p(y1>0 or !y1 and x1>0); //a在上半平面或正x轴bool q(y2>0 or !y2 and x2>0); //b在上半平面或正x轴if(p!=q) return p>q; //上半平面排前else return x1*y2>x2*y1; //同半平面逆时针排序(叉积)
}
signed main(){cin>>n>>q;for(int i=1,x,y;i<=n;++i){cin>>x>>y;int g(__gcd(abs(x),abs(y))); //约分统一方向if(g) x/=g,y/=g;if(!mp[{x,y}].size()) dir.push_back({x,y}); //新方向进列表mp[{x,y}].push_back(i); //怪物加入方向组}sort(dir.begin(),dir.end(),cmp); //逆时针排方向for(int i=0;i<dir.size();++i){cnt[i+1]=mp[dir[i]].size(); //记方向怪物数for(int k:mp[dir[i]]) id[k]=i+1; //记怪物方向编号}for(int i=1;i<=dir.size();++i) pre[i]=pre[i-1]+cnt[i]; //前缀和for(int a,b;q--;){cin>>a>>b;int x(id[a]),y(id[b]); //怪物方向编号if(x==y) cout<<cnt[x]<<'\n'; //同方向即该方向所有怪物else if(x>y) cout<<pre[x]-pre[y-1]<<'\n'; //逆时针区间和else cout<<pre[dir.size()]+pre[x]-pre[y-1]<<'\n'; //顺时针绕一圈}
}F - Diagonal Separation 2
简单优化dp，其实就是维护一个形状而已。
void solve(){cin>>n;up(i,1,n){cin>>s[i];s[i]=" "+s[i];}memset(f,0x3f,sizeof f);memset(minl,0x3f,sizeof minl);up(i,1,n){up(j,1,n){pre[i][j]=pre[i][j-1]+(s[i][j]=='#');}dn(j,n,1){suf[i][j]=suf[i][j+1]+(s[i][j]=='.');}}up(j,0,n){f[1][j]=min(f[1][j],pre[1][j]+suf[1][j+1]);}up(i,2,n){memset(minl,0x3f,sizeof minl);dn(j,n,0){minl[j]=min(minl[j+1],f[i-1][j]);}up(j,0,n){f[i][j]=minl[j]+pre[i][j]+suf[i][j+1];//up(k,j,n)f[i][j]=min(f[i][j],f[i-1][k]+pre[i][j]+suf[i][j+1]);}}int ans=inf;up(i,0,n){ans=min(ans,f[n][i]);}cout<<ans;
}