我这个傻逼被治了一下午。
大好的橘势，两个小时6T，去看L，哇傻逼题。然后我跑的最短路T到自闭
最后十几分钟去想了下A，一直在想如何表示状态。。就是想不到二进制搞一下。。。
然后游戏结束了。。以后我就是蓝名之耻了。(注：此称号送给一场比赛里排名最低的蓝名选手)
所以非常凄惨到现在也只有8个，，我还想AK来着，，毕竟有紫名选手AK了，那我1800多分也差不多叭
注意：堆优化dijkstra的复杂度是mlogm！！！
注意：堆优化dijkstra的复杂度是mlogm！！！
注意：堆优化dijkstra的复杂度是mlogm！！！
A：貌似有奇怪的式子或者更佳的转移方式？
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+;
ll f[][];
int n;
void init(){
f[^][]=;
int cnt=;
while (cnt<n){
cnt++;
int i=cnt%;
f[i^][]=f[i][]; f[i^][]=f[i][]; f[i^][]=f[i][]; f[i^][]=f[i][]+f[i][]; f[i^][]=f[i][]; f[i^][]=f[i][]; f[i^][]=f[i][]+f[i][]; f[i^][]=f[i][]+f[i][]+f[i][]; for(int j=;j<=;j++){
f[i^][j]%=mod;
}
}
}
int main(){
ios::sync_with_stdio(false);
cin>>n;
init();
if(n&){
cout<<min(f[][],f[][]);
} else{
cout<<max(f[][],f[][]);
}
}
B：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
string s;
int main(){
ios::sync_with_stdio(false);
cin>>s;
int nc=,ns=;
for(int i=;i<s.length();i++){
if(s[i]=='C'&&nc<){
nc++;ns=;
cout<<'B';
} else if(s[i]=='C'&&nc==){
cout<<'P';
nc=;ns=;
} else if(s[i]=='S'&&ns<){
ns++;cout<<'D';nc=;
} else{
ns=;nc=;cout<<'T';
}
}
}
C：
D：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;ll s;
int main(){
ios::sync_with_stdio(false);
cin>>n;
while (n--){
cin>>s;
ll l=,r=15e8;
while (l<=r){
ll mid = l+r>>;
if((mid+)*mid/<=s){
l=mid+;
} else {
r=mid-;
}
}
cout<<r<<endl;
}
}
E：
F：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+;
int n,m;
struct Edge{
int u,v;
}e[N];
int a[N],ans[N];
int fa[N];
int find(int x){
return x==fa[x]?x:fa[x]=find(fa[x]);
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=;i<=m;i++){
fa[i]=i;
cin>>e[i].v>>e[i].u;
}
for(int i=;i<=m;i++){
cin>>a[i];
}
ans[m+]=n;
for(int i=m;i>=;i--){
int u=find(e[a[i]].u),v=find(e[a[i]].v);
if(u==v){
ans[i]=ans[i+];
} else{
fa[u]=v;
ans[i]=ans[i+]-;
}
}
for(int i=;i<=m+;i++){
cout<<ans[i]<<endl;
}
}
G：
H：被坑了好久才反应过来
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
double n,a,p;
int main(){
scanf("%lf%lf%lf",&n,&a,&p);
p/=;
double x = p-(-p);
n+=a*x;
printf("%.10f\n",n);
}
I：判点在多边形内部板子
#include <bits/stdc++.h>
using namespace std;
typedef double db;
const db eps=1e-;
const db pi=acos(-);
int sign(db k){
if (k>eps) return ; else if (k<-eps) return -; return ;
}
int cmp(db k1,db k2){return sign(k1-k2);}
int inmid(db k1,db k2,db k3){ return sign(k1-k3)*sign(k2-k3)<=;}
struct point {
db x,y;
point operator + (const point &k1) const{return (point){k1.x+x,k1.y+y};}
point operator - (const point &k1) const{return (point){x-k1.x,y-k1.y};}
point operator * (db k1) const{return (point){x*k1,y*k1};}
point operator / (db k1) const{return (point){x/k1,y/k1};}
bool operator == (const point &k1) const{return cmp(x,k1.x)==&&cmp(y,k1.y)==;}
db abs(){ return sqrt(x*x+y*y);}
db abs2(){return x*x+y*y;}
db dis(point k1){ return (*this-k1).abs();}
bool operator<(const point &k1)const{
int c = cmp(x,k1.x);
if(c)return c==-;
return cmp(y,k1.y)==-;
}
};
int inmid(point k1,point k2,point k3){return inmid(k1.x,k2.x,k3.x)&&inmid(k1.y,k2.y,k3.y);}
db cross(point k1,point k2){ return k1.x*k2.y-k1.y*k2.x;}
int onS(point k1,point k2,point q){return inmid(k1,k2,q)&&sign(cross(k1-q,k2-k1))==;}
db dot(point k1,point k2){ return k1.x*k2.x+k1.y*k2.y;}
vector<point> convexHull(vector<point> ps){
int n = ps.size();if(n<=)return ps;
sort(ps.begin(),ps.end());
vector<point> qs(n*);int k = ;
for(int i=;i<n;qs[k++]=ps[i++])
while (k>&&cross(qs[k-]-qs[k-],ps[i]-qs[k-])<=)--k;
for(int i=n-,t=k;i>=;qs[k++]=ps[i--])
while (k>t&&cross(qs[k-]-qs[k-],ps[i]-qs[k-])<=)--k;
qs.resize(k-);
return qs;
}
int contain(vector<point>A,point q){//0外边
int pd=;A.push_back(A[]);
for(int i=;i<A.size();i++){
point u=A[i-],v=A[i];
if(onS(u,v,q))return ;if (cmp(u.y,v.y)>) swap(u,v);
if(cmp(u.y,q.y)>=||cmp(v.y,q.y)<)continue;
if(sign(cross(u-v,q-v))<)pd^=;
}
return pd<<;
}
vector<point>p[];
int s,r,m;
int n;
point tmp;
int main(){
scanf("%d%d%d",&s,&r,&m);
for(int i=;i<=s;i++){
scanf("%lf%lf",&tmp.x,&tmp.y);p[].push_back(tmp);
}
for(int i=;i<=r;i++){
scanf("%lf%lf",&tmp.x,&tmp.y);p[].push_back(tmp);
}
for(int i=;i<=m;i++){
scanf("%lf%lf",&tmp.x,&tmp.y);p[].push_back(tmp);
}
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%lf%lf",&tmp.x,&tmp.y);
if(contain(p[],tmp)){
printf("Sheena\n");
} else if(contain(p[],tmp)){
printf("Rose\n");
} else if(contain(p[],tmp)){
printf("Maria\n");
} else{
printf("Outside\n");
}
}
}
J：反着来维护区间和
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+;
int n;
int a[N],c[N];
int lowbit(int k){ return k&-k;}
void upd(int pos,int num){
while (pos<=1e6+){
c[pos]+=num;
pos+=lowbit(pos);
}
}
int sum(int pos){
int res = ;
while (pos>){
res+=c[pos];
pos-=lowbit(pos);
}
return res;
}
int ans[N];
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++){
cin>>a[i];a[i]++;
ans[i] = n-(i--sum(a[i]-));
upd(a[i],);
}
for(int i=;i<=n;i++){
printf("%d\n",ans[i]);
}
}
K：dij加一维维护模数。。好傻逼啊我的天。。为什么我这么傻逼啊。。因为终点只能走一次所以不能来更新其他节点，判断一下就好。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+;
struct Edge{int v,w,nxt;};
Edge e[];
int head[],cnt=;
void addEdge(int u,int v,int w){
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].nxt=head[u];
head[u]=cnt;
}
int dis[][];
struct node{
int u,d,res;
bool operator <(const node&rhs)const {
return d>rhs.d;
}
};
int n,m;
void Dijkstra(){
for(int i=;i<=n;i++)for(int j=;j<;j++)dis[i][j]=;
dis[][]=;
priority_queue<node> Q;
Q.push((node){,,});
while (!Q.empty()){
node fr=Q.top();Q.pop();
int u=fr.u,d=fr.d,r=fr.res;
if(d>dis[u][r])continue;
if(u==n)continue;
for(int i=head[u];i;i=e[i].nxt){
int v = e[i].v,w=e[i].w;
if(dis[u][r]+w<dis[v][(r+)%]){
dis[v][(r+)%]=dis[u][r]+w;
Q.push((node){v,dis[v][(r+)%],(r+)%});
}
}
}
}
int dep[N];
void pa(){cout<<"me"<<endl;}
void pb(){cout<<"Gon"<<endl;}
void pc(){cout<<"Killua"<<endl;}
int main(){
ios::sync_with_stdio(false);
cin>>n>>m;
int u,v,w;
while(m--){
cin>>u>>v>>w;
addEdge(u,v,w);
addEdge(v,u,w);
}
Dijkstra();
int a=dis[n][],b=dis[n][],c=dis[n][];
if(a<=b&&a<=c){
pa();
if(b<=c)pb(),pc();
else pc(),pb();
} else if(b<=a&&b<=c){
pb();
if(a<=c)pa(),pc();
else pc(),pa();
} else{
pc();
if(b<=a)pb(),pa();
else pa(),pb();
}
}
L：为什么这么傻逼的O(n)的做法我当时会想不到呢。。。
#include <bits/stdc++.h>
#define pii pair<int,int>
#define mk(a,b) make_pair(a,b)
using namespace std;
typedef long long ll;
vector<int> g[];
map<pii,int> mp;
struct Node{
int x,y;
}node[];
bool cmp(Node a,Node b){ return a.x<b.x;}
int n,l;
int dep[];
void dfs(int v){
for(int i=;i<g[v].size();i++){
int u = g[v][i];
if(dep[v]+>dep[u]) {
dep[u]=dep[v]+;
dfs(u);
}
}
}
int main(){
scanf("%d%d",&n,&l);
node[]={,};
mp[mk(,)]=;
for(int i=;i<=n;i++){
scanf("%d%d",&node[i].x,&node[i].y);
}
sort(node+,node++n,cmp);
for(int i=;i<=n;i++){
mp[mk(node[i].x,node[i].y)]=i;
}
node[n+]={l,};
mp[mk(l,)]=n+;
for(int i=;i<=n;i++){
for(int j=;j<=;j++){
for(int k=-(-j);k<=(-j);k++){
if(!mp.count(mk(node[i].x+j,node[i].y+k)))continue;
if(abs(j)+abs(k)<=){
g[i].push_back(mp[mk(node[i].x+j,node[i].y+k)]);
}
}
}
}
memset(dep,-0x3f, sizeof(dep));
dep[]=;
for(int i=;i<=n;i++){
for(int j=;j<g[i].size();j++){
int u = g[i][j];
dep[u]=max(dep[u],dep[i]+);
}
}
printf("%d\n",dep[n+]-);
}
总结。打的太烂了。L被治了，A题好像也没带脑子。K看了两眼没兴趣，其他的没看。。。在两个小时以后就失去了生命迹象。。。
补题的话。如果下周四补了就是补了，否则应该就是不补了。。。(囤了好十几道题了我好慌啊！！！)
md等我过几天上紫了非得开教练模式爽一爽。越切越想要教练模式。。。
