您的位置: 首页  >  IT文章  >  gym 101858

gym 101858

分类: IT文章 • 2025-02-03 22:21:43

我这个傻逼被治了一下午。

大好的橘势，两个小时6T，去看L，哇傻逼题。然后我跑的最短路T到自闭  

最后十几分钟去想了下A，一直在想如何表示状态。。就是想不到二进制搞一下。。。

然后游戏结束了。。以后我就是蓝名之耻了。(注：此称号送给一场比赛里排名最低的蓝名选手)

所以非常凄惨到现在也只有8个，，我还想AK来着，，毕竟有紫名选手AK了，那我1800多分也差不多叭

注意：堆优化dijkstra的复杂度是mlogm！！！

注意：堆优化dijkstra的复杂度是mlogm！！！

注意：堆优化dijkstra的复杂度是mlogm！！！

A：貌似有奇怪的式子或者更佳的转移方式？

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const ll mod = 1e9+7;
 5 ll f[2][8];
 6 int n;
 7 void init(){
 8     f[0^1][7]=1;
 9     int cnt=0;
10     while (cnt<n){
11         cnt++;
12         int i=cnt%2;
13         f[i^1][0]=f[i][7];
14 
15         f[i^1][1]=f[i][6];
16 
17         f[i^1][2]=f[i][5];
18 
19         f[i^1][3]=f[i][7]+f[i][4];
20 
21         f[i^1][4]=f[i][3];
22 
23         f[i^1][5]=f[i][2];
24 
25         f[i^1][6]=f[i][7]+f[i][1];
26 
27         f[i^1][7]=f[i][6]+f[i][3]+f[i][0];
28 
29         for(int j=0;j<=7;j++){
30             f[i^1][j]%=mod;
31         }
32     }
33 }
34 int main(){
35     ios::sync_with_stdio(false);
36     cin>>n;
37     init();
38     if(n&1){
39         cout<<min(f[0][7],f[1][7]);
40     } else{
41         cout<<max(f[0][7],f[1][7]);
42     }
43 }
View Code

B：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 string s;
 5 int main(){
 6     ios::sync_with_stdio(false);
 7     cin>>s;
 8     int nc=0,ns=0;
 9     for(int i=0;i<s.length();i++){
10         if(s[i]=='C'&&nc<2){
11             nc++;ns=0;
12             cout<<'B';
13         } else if(s[i]=='C'&&nc==2){
14             cout<<'P';
15             nc=0;ns=0;
16         } else if(s[i]=='S'&&ns<2){
17             ns++;cout<<'D';nc=0;
18         } else{
19             ns=0;nc=0;cout<<'T';
20         }
21     }
22 }
View Code

C：

D：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 int n;ll s;
 5 int main(){
 6     ios::sync_with_stdio(false);
 7     cin>>n;
 8     while (n--){
 9         cin>>s;
10         ll l=0,r=15e8;
11         while (l<=r){
12             ll mid = l+r>>1;
13             if((mid+1)*mid/2<=s){
14                 l=mid+1;
15             } else {
16                 r=mid-1;
17             }
18         }
19         cout<<r<<endl;
20     }
21 }
View Code

E：

F：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int N = 1e5+5;
 5 int n,m;
 6 struct Edge{
 7     int u,v;
 8 }e[N];
 9 int a[N],ans[N];
10 int fa[N];
11 int find(int x){
12     return x==fa[x]?x:fa[x]=find(fa[x]);
13 }
14 int main(){
15     ios::sync_with_stdio(false);
16     cin>>n>>m;
17     for(int i=1;i<=m;i++){
18         fa[i]=i;
19         cin>>e[i].v>>e[i].u;
20     }
21     for(int i=1;i<=m;i++){
22         cin>>a[i];
23     }
24     ans[m+1]=n;
25     for(int i=m;i>=1;i--){
26         int u=find(e[a[i]].u),v=find(e[a[i]].v);
27         if(u==v){
28             ans[i]=ans[i+1];
29         } else{
30             fa[u]=v;
31             ans[i]=ans[i+1]-1;
32         }
33     }
34     for(int i=2;i<=m+1;i++){
35         cout<<ans[i]<<endl;
36     }
37 }
View Code

G：

H：被坑了好久才反应过来

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 double n,a,p;
 5 int main(){
 6     scanf("%lf%lf%lf",&n,&a,&p);
 7     p/=100;
 8     double x = p-(1-p);
 9     n+=a*x;
10     printf("%.10f
",n);
11 }
View Code

I：判点在多边形内部板子

#include <bits/stdc++.h>
using namespace std;
typedef double db;
const db eps=1e-6;
const db pi=acos(-1);
int sign(db k){
    if (k>eps) return 1; else if (k<-eps) return -1; return 0;
}
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)<=0;}
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)==0&&cmp(y,k1.y)==0;}
    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==-1;
        return cmp(y,k1.y)==-1;
    }
};
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))==0;}
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<=1)return ps;
    sort(ps.begin(),ps.end());
    vector<point> qs(n*2);int k = 0;
    for(int i=0;i<n;qs[k++]=ps[i++])
        while (k>1&&cross(qs[k-1]-qs[k-2],ps[i]-qs[k-2])<=0)--k;
    for(int i=n-2,t=k;i>=0;qs[k++]=ps[i--])
        while (k>t&&cross(qs[k-1]-qs[k-2],ps[i]-qs[k-2])<=0)--k;
    qs.resize(k-1);
    return qs;
}
int contain(vector<point>A,point q){//0外边
    int pd=0;A.push_back(A[0]);
    for(int i=1;i<A.size();i++){
        point u=A[i-1],v=A[i];
        if(onS(u,v,q))return 1;if (cmp(u.y,v.y)>0) swap(u,v);
        if(cmp(u.y,q.y)>=0||cmp(v.y,q.y)<0)continue;
        if(sign(cross(u-v,q-v))<0)pd^=1;
    }
    return pd<<1;
}
vector<point>p[5];
int s,r,m;
int n;
point tmp;
int main(){
    scanf("%d%d%d",&s,&r,&m);
    for(int i=1;i<=s;i++){
        scanf("%lf%lf",&tmp.x,&tmp.y);p[1].push_back(tmp);
    }
    for(int i=1;i<=r;i++){
        scanf("%lf%lf",&tmp.x,&tmp.y);p[2].push_back(tmp);
    }
    for(int i=1;i<=m;i++){
        scanf("%lf%lf",&tmp.x,&tmp.y);p[3].push_back(tmp);
    }
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lf%lf",&tmp.x,&tmp.y);
        if(contain(p[1],tmp)){
            printf("Sheena
");
        } else if(contain(p[2],tmp)){
            printf("Rose
");
        } else if(contain(p[3],tmp)){
            printf("Maria
");
        } else{
            printf("Outside
");
        }
    }
}
View Code

J：反着来维护区间和

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int N = 1e6+6;
 5 int n;
 6 int a[N],c[N];
 7 int lowbit(int k){ return k&-k;}
 8 void upd(int pos,int num){
 9     while (pos<=1e6+1){
10         c[pos]+=num;
11         pos+=lowbit(pos);
12     }
13 }
14 int sum(int pos){
15     int res = 0;
16     while (pos>0){
17         res+=c[pos];
18         pos-=lowbit(pos);
19     }
20     return res;
21 }
22 int ans[N];
23 int main(){
24     scanf("%d",&n);
25     for(int i=1;i<=n;i++){
26         cin>>a[i];a[i]++;
27         ans[i] = n-(i-1-sum(a[i]-1));
28         upd(a[i],1);
29     }
30     for(int i=1;i<=n;i++){
31         printf("%d
",ans[i]);
32     }
33 }
View Code

K：dij加一维维护模数。。好傻逼啊我的天。。为什么我这么傻逼啊。。因为终点只能走一次所以不能来更新其他节点，判断一下就好。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int N = 2e5+5;
 5 struct Edge{int v,w,nxt;};
 6 Edge e[500010];
 7 int head[100010],cnt=0;
 8 void addEdge(int u,int v,int w){
 9     e[++cnt].v=v;
10     e[cnt].w=w;
11     e[cnt].nxt=head[u];
12     head[u]=cnt;
13 }
14 int dis[100010][3];
15 struct node{
16     int u,d,res;
17     bool operator <(const node&rhs)const {
18         return d>rhs.d;
19     }
20 };
21 int n,m;
22 void Dijkstra(){
23     for(int i=1;i<=n;i++)for(int j=0;j<3;j++)dis[i][j]=2147483647;
24     dis[1][0]=0;
25     priority_queue<node> Q;
26     Q.push((node){1,0,0});
27     while (!Q.empty()){
28         node fr=Q.top();Q.pop();
29         int u=fr.u,d=fr.d,r=fr.res;
30         if(d>dis[u][r])continue;
31         if(u==n)continue;
32         for(int i=head[u];i;i=e[i].nxt){
33             int v = e[i].v,w=e[i].w;
34             if(dis[u][r]+w<dis[v][(r+1)%3]){
35                 dis[v][(r+1)%3]=dis[u][r]+w;
36                 Q.push((node){v,dis[v][(r+1)%3],(r+1)%3});
37             }
38         }
39     }
40 }
41 int dep[N];
42 void pa(){cout<<"me"<<endl;}
43 void pb(){cout<<"Gon"<<endl;}
44 void pc(){cout<<"Killua"<<endl;}
45 int main(){
46     ios::sync_with_stdio(false);
47     cin>>n>>m;
48     int u,v,w;
49     while(m--){
50         cin>>u>>v>>w;
51         addEdge(u,v,w);
52         addEdge(v,u,w);
53     }
54     Dijkstra();
55     int a=dis[n][0],b=dis[n][1],c=dis[n][2];
56     if(a<=b&&a<=c){
57         pa();
58         if(b<=c)pb(),pc();
59         else pc(),pb();
60     } else if(b<=a&&b<=c){
61         pb();
62         if(a<=c)pa(),pc();
63         else pc(),pa();
64     } else{
65         pc();
66         if(b<=a)pb(),pa();
67         else pa(),pb();
68     }
69 }
View Code

L：为什么这么傻逼的O(n)的做法我当时会想不到呢。。。

 1 #include <bits/stdc++.h>
 2 #define pii pair<int,int>
 3 #define mk(a,b) make_pair(a,b)
 4 using namespace std;
 5 typedef long long ll;
 6 vector<int> g[100005];
 7 map<pii,int> mp;
 8 struct Node{
 9     int x,y;
10 }node[100005];
11 bool cmp(Node a,Node b){ return a.x<b.x;}
12 int n,l;
13 int dep[100005];
14 void dfs(int v){
15     for(int i=0;i<g[v].size();i++){
16         int u = g[v][i];
17         if(dep[v]+1>dep[u]) {
18             dep[u]=dep[v]+1;
19             dfs(u);
20         }
21     }
22 }
23 int main(){
24     scanf("%d%d",&n,&l);
25     node[1]={0,0};
26     mp[mk(0,0)]=0;
27     for(int i=1;i<=n;i++){
28         scanf("%d%d",&node[i].x,&node[i].y);
29     }
30     sort(node+1,node+1+n,cmp);
31     for(int i=1;i<=n;i++){
32         mp[mk(node[i].x,node[i].y)]=i;
33     }
34     node[n+1]={l,0};
35     mp[mk(l,0)]=n+1;
36     for(int i=0;i<=n;i++){
37         for(int j=1;j<=5;j++){
38             for(int k=-(5-j);k<=(5-j);k++){
39                 if(!mp.count(mk(node[i].x+j,node[i].y+k)))continue;
40                 if(abs(j)+abs(k)<=5){
41                     g[i].push_back(mp[mk(node[i].x+j,node[i].y+k)]);
42                 }
43             }
44         }
45     }
46     memset(dep,-0x3f, sizeof(dep));
47     dep[0]=0;
48     for(int i=0;i<=n;i++){
49         for(int j=0;j<g[i].size();j++){
50             int u = g[i][j];
51             dep[u]=max(dep[u],dep[i]+1);
52         }
53     }
54     printf("%d
",dep[n+1]-1);
55 }
View Code

总结。打的太烂了。L被治了，A题好像也没带脑子。K看了两眼没兴趣，其他的没看。。。在两个小时以后就失去了生命迹象。。。

补题的话。如果下周四补了就是补了，否则应该就是不补了。。。(囤了好十几道题了我好慌啊！！！)

md等我过几天上紫了非得开教练模式爽一爽。越切越想要教练模式。。。

相关推荐