DAY2

依旧是yyx出题

依旧毒瘤

滞空(jump/1s/64M)

题目描述：

pyy在平面上第一象限内发现了顺序n个平台(她可以踩在这些平台上，但必须从第i-1号平台跳跃至i-1号平台)，这些平台的横坐标互异且单调递增，从i号平台出发依次跳跃经过2-->n号平台不允许落地。

给出pyy的质量m和重力加速度g(重力沿y轴负方向)，考虑理想情况下，求pyy需要消耗的最小能量(不考虑落至平台冲量(即落至平台后速度为0))(单位J)。

设E为能量，m为质量，v为速度，x为位移，a为加速度，t为时间，h为两个点高度差。

能量守恒指在本题中初始动能视为人体能量消耗；

牛顿第二定律给出加速运动中，加速度与位移间关系的公式；

动能定理和重力势能公式给出能量计算公式。

样例输入

样例输出

499122214J

一个鬼畜的物理题。。。

pyy在中子星上以光速跳跃？？？

我自闭了

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const LL mod = ;

inline void rd(LL &x)

{

    x=;int f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

}

LL n,m,x[],y[],g,ans;

LL qpow(LL a)

{

    LL res=,k=mod-;

    while(k)

    {

        if(k&)res=res*a%mod;

        a=a*a%mod;

        k>>=;

    }

    return res;

}

LL _2 = qpow();

void down(LL x,LL h){x%=mod;h%=mod;    ans += (x*x*m%mod)*qpow(*h);    ans%=mod;}

void up(LL x,LL h)    {x%=mod;h%=mod;    ans += (m*h%mod) + ( (x*x*m%mod) *qpow(*h) )%mod;    ans%=mod;}

void pi_4(LL x){x%=mod;    ans += (m*x%mod)*_2;    ans%=mod;}

void solve()

{

    scanf("%lld%lld%lld",&n,&m,&g);

    rd(x[]);    rd(y[]);

    for(int i=;i<=n;i++)

    {

        rd(x[i&]);    rd(y[i&]);

        if(y[i&]>y[!(i&)])    up(x[i&]-x[!(i&)],y[i&]-y[!(i&)]);

        if(y[i&]<y[!(i&)])    down(x[i&]-x[!(i&)],y[!(i&)]-y[i&]);

        if(y[i&]==y[!(i&)])    pi_4(x[i&]-x[!(i&)]);

    }

    printf("%lldJ",ans*g%mod);

}

int main()

{

    freopen("jump.in","r",stdin);

    freopen("jump.out","w",stdout);

    solve();

    fclose(stdin);

    fclose(stdout);

    return ;

}

放爆竹（bomb/1s/64M)

1 题目描述

  小明和小辉一起放爆竹。

  小辉将很多地雷和春雷穿成了n串。因为地雷和春雷爆炸的声音是不一样的，所以串起来以后，爆炸的声音也是不一样的。

  小辉原本想让小明告诉他，如果同时点燃n串雷，最多会有多长的时间至少有两串雷爆炸的声音是一样的。

  但是小辉觉得这个问题真是太简单了，所以决定问小明，如果在山谷中（有回音）同时点燃n串雷，那最多会有多长的时间至少有两串雷爆炸的声音是一样的呢？

  小辉认为一枚春雷或者地雷爆炸都需要1ms，且山谷中的回音不减弱，并且小辉给出的雷串不会是任意一个雷串的重复（不管重复的雷串是否存在，即无论如何都不会存在类似于 01010101的雷串）。

2 输入

2.1 输入格式

  第一行，一个数，表示有n串雷。

  接下来n行，其中第i行一个01字符串描述小辉的第i串雷，其中0表示春雷，1表示地雷。

2.2 样例1输入





2.3 样例2输入








3 输出


3.1 输出格式


  一行，一个数表示小明给出的答案。


3.2 样例1输出








3.3 样例2输出








4 样例解释


4.1 样例1解释


  第3串雷0100爆炸后得到的声音串0100010001000100…


  第4串雷010爆炸后得到声音串010010010010010…


  两个声音串的前4位是一样的，所以小辉前4ms听到的声音是一样的。




















#include <bits/stdc++.h>

using std::max;

using std::strlen;

const int N=,Mlen=,Node=N*Mlen*;

int n,len[N],ans;

char s[N][Mlen];

struct Trie{

    int son[Node][],node,app[Node],dep[Node],f[Node];

    void init() {

        son[][]=son[][]=;

        app[]=dep[]=;

    }

    int newnode(int d){

        ++node;

        son[node][]=son[node][]=;

        dep[node]=d;

        app[node]=;

        return node;

    }

    void insert(char *s,int len,int t) {

        int p=,add=;

        while (t) {

            for (int i=;i<len && add<=;++i) {

                int &x=son[p][s[i]-''],pp=p;

                p=x?x:x=newnode(dep[p]+); f[p]=pp;

                app[p]++; add++;

            }

            t--;

        }

    }

    int FindAns() {

        int ans=;

        for (int i=;i<=node;++i) if (app[i]>=) {

            ans=max(ans,dep[i]);

        }

//        for (int i=1;i<=node;++i) if (app[i]>=2 && ans==dep[i]) {

//            int p=i;

//            while (p) {

//                putchar((p==son[f[p]][1])+'0');

//                p=f[p];

//            }

//            putchar('\n');

//            break;

//        }

        return ans;

    }

}tr;

void Init() {

    scanf("%d",&n);

    for (int i=;i<=n;++i) {

        scanf("%s",s[i]); len[i]=strlen(s[i]);

    }

}

void Solve() {

    tr.init();

    for (int i=;i<=n;++i) {

        tr.insert(s[i],len[i],(-)/len[i]+);

    }

    printf("%d\n",tr.FindAns());

}

int main() {

    freopen("bomb.in","r",stdin);

    freopen("bomb.out","w",stdout);

    Init();

    Solve();

    fclose(stdin);

    fclose(stdout);

    return ;

}




以上是正解std


我的菜鸡做法：


也是字典树，先不考虑重复的情况，把n个01串在字典树上建出来，并且多记录一个数组num表示经过某一条边的字符串的数量


然后遍历字典树中num大于1的边，每次遇到结尾的标记end就将这一个字符串重新复制一遍接在现在节点的下方


在遍历的时候记录数量，然后取max就行了


由于这是有需要的时候才复制，应该会比上面的题解快一些吧rwr




#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<iomanip>

#include<cmath>

#include<cstring>

#include<string>

#include<algorithm>

#include<queue>

using namespace std;

int n;

char s[][];

int ch[][];

int end[];

int num[];

int cnt,id;

int ans;

inline void build(int x)

{

    int now=;

    for(int i=;i<strlen(s[x]);i++)

    {

        int c=s[x][i]-'';

        if(!ch[now][c]) ch[now][c]=++cnt;

        now=ch[now][c];

        num[now]++;

    }

    end[now]=(++id);

}

void dfs(int now,int an)

{

    ans=max(ans,an);

    printf("%d ",ans);

    if(num[now]>&&end[now]!=)

    {

        int noow=now;

        for(int j=;j<strlen(s[end[now]]);j++)

        {

            int c=s[end[now]][j]-'';

            if(!ch[noow][c]) ch[noow][c]=++cnt;

            noow=ch[noow][c];

            num[noow]++;

        }

        end[noow]=end[now];

    }

    for(int i=;i<=;i++)

    {

        if(num[ch[now][i]]>)

        {

            if(ch[now][i]==) continue;

            else

            {

                dfs(ch[now][i],an+);

            }

        }

        else continue;

    }

}

int main()

{

//    freopen("bomb.in","r",stdin);

//    freopen("bomb.out","w",stdout);

    scanf("%d",&n);

    for(int i=;i<=n;i++)

    {

        scanf("%s",s[i]);

        build(i);

    }

    num[]=n;

    dfs(,);

    printf("%d\n",ans);

}




pyy整队(queue,1s,128M)


问题描述：


　　众所周知pyy当了班长，服务于民。一天体育课，趁体育老师还没来，pyy让班里n个同学先排好队。老师不在，同学们开始玩起了手机。站在队伍前端玩手机，前面的人少了，谁都顶不住。于是陆陆续续有人往队伍最后躲去，但大家都沉迷某骗氪手游，忘记了老师说前面位置有空缺要补齐的要求。一些同学还时不时地低头问向指挥队伍的班长pyy，排在自己前面成绩最好的同学是谁，这样自己才能心安理得放心大胆的继续玩手机。


  这时老师来了，同学们在可以忽略不计的时间内收好了手机。看着到处充满空缺的队伍，体育老师勃然大怒并借题发挥，以扬体育组声威，限pyy以最快的时间整顿队伍。由于是体育老师，并看不出来队伍的位置后移了，老师只关心队伍是否整齐没有空缺。


  老师给了pyy一次移动一名同学的权力，因此pyy无法使用技能“向前看齐”。pyy的哥哥强制要求你帮助pyy回答之前同学们的问题，并告诉pyy在老师来之后，至少移动多少个同学可以使队伍整齐。


输入格式


　　第一行为两个整数n,m(1<=n,m<=1e5)，表示有n位同学，在老师来之前进行了m次小动作。


  第二行为n个以空格隔开的整数a1,a2,…,an(1<=ai<=1e7) ，表示初始时队伍中第i位同学的年级成绩排名(数据保证不会有两人成绩重复)。


  接下来m行描述同学们的行为，每行由一个字符A或S和一个整数x∈{ai|1<=i<=n} 构成。若为A,x，则表示年级成绩排名为x的同学向pyy询问自己前面成绩最好的是哪位同学；若为M,x，则表示年级成绩排名为x的同学此时躲到了当前队伍的最尾端(不存在队尾同学躲向队尾)。


输出格式


前m个操作中对于每个同学的询问，顺序输出所询问同学的年级成绩排名，并以换行隔开。若询问学生不存在则输出-1。


最后一行输出至少移动多少位同学，使得队伍整齐。


样例输入





A

M

M

A

A 




样例输出








数据范围


对于10%的数据 n<=10,m<=20


对于30%的数据 n<=10^3,m<=10^4


对于100%的数据  n<=10^5,m<=10^5,ai<=10^7


正解


离散化成绩+权值线段树维护每个人的位置。每次移动将人的位置移动到n+k(k为操作次数)。


注意一个细节，询问是寻找x前面权值最小的元素，那么需要获取实际情况中pre_x的权值使用链表模拟即可。


最后枚举最终队列的队首，判断长度为n范围外有多少人需要调整。(其实什么方法都可以搞搞)


部分分


对于10%的数据：模拟


对于30%的数据： n^2暴力模拟每个时刻的情况




#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const LL mod = ;

inline void rd(LL &x)

{

    x=;int f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

}

LL n,m,x[],y[],g,ans;

LL qpow(LL a)

{

    LL res=,k=mod-;

    while(k)

    {

        if(k&)res=res*a%mod;

        a=a*a%mod;

        k>>=;

    }

    return res;

}

LL _2 = qpow();

void down(LL x,LL h){x%=mod;h%=mod;    ans += (x*x*m%mod)*qpow(*h);    ans%=mod;}

void up(LL x,LL h)    {x%=mod;h%=mod;    ans += (m*h%mod) + ( (x*x*m%mod) *qpow(*h) )%mod;    ans%=mod;}

void pi_4(LL x){x%=mod;    ans += (m*x%mod)*_2;    ans%=mod;}

void solve()

{

    scanf("%lld%lld%lld",&n,&m,&g);

    rd(x[]);    rd(y[]);

    for(int i=;i<=n;i++)

    {

        rd(x[i&]);    rd(y[i&]);

        if(y[i&]>y[!(i&)])    up(x[i&]-x[!(i&)],y[i&]-y[!(i&)]);

        if(y[i&]<y[!(i&)])    down(x[i&]-x[!(i&)],y[!(i&)]-y[i&]);

        if(y[i&]==y[!(i&)])    pi_4(x[i&]-x[!(i&)]);

    }

    printf("%lldJ",ans*g%mod);

}

int main()

{

    freopen("jump.in","r",stdin);

    freopen("jump.out","w",stdout);

    solve();

    fclose(stdin);

    fclose(stdout);

    return ;

}


												


																

最新文章
	

    
						
  1. Java 异常java.lang.IllegalArgumentException: Illegal group reference
		
    2. 
						
  2. FIleText转换为JSONObject对象
		
    3. 
						
  3. ejb 远程调用
		
    4. 
						
  4. OpenCv，EmguCv及.net之间的互动(The Interaction of OpenCv, EmguCv AND .net)
		
    5. 
						
  5. java第三章动手动脑
		
    6. 
						
  6. 开启telnet的几种方法
		
    7. 
						
  7. Doing well in your courses  ---- a guide by Andrej Karpathy
		
    8. 
						
  8. C#转换日期类型
		
    9. 
						
  9. Jquery 模糊匹配ID
		
    10. 
						
  10. 流媒体开发之-腾讯体育NBA视频点播解析
		
    11. 
						
  11. 最近纠结致死的一个java报错java.net.SocketException: Connection reset 终于得到解决
		
    12. 
						
  12. php截取中文字符串，英文字符串，中英文字符串长度的方法
		
    13. 
						
  13. Linux安装MariaDB（Mysql）和简单配置
		
    14. 
						
  14. Dynamics CRM OData方式进行增删改查时报错的问题
		
    15. 
						
  15. API响应
		
    16. 
						
  16. 一个mysqldump的报错
		
    17. 
						
  17. PTA3
		
    18. 
						
  18. 配置opensips经验总结
		
    19. 
						
  19. gcc/g++多版本切换   (ubuntu18.04)
		
    20. 
						
  20. 024 Yarn核心生态系统
		
    21. 
		

	


热门文章
	

    
									
  1. Windows下nginx的启动，重启，关闭功能
			
    2. 
						
  2. 生产者消费者问题--synchronized
			
    3. 
						
  3. 更优雅地关闭资源 - try-with-resource
			
    4. 
						
  4. mvn高级构建
			
    5. 
						
  5. 我的前端组件 ---- 16:9固定宽高比例的div
			
    6. 
						
  6. 10.17小作业  基于TCP开发一款远程CMD程序
			
    7. 
						
  7. 【winfrom-右击快捷菜单】右击或左击时显示快捷菜单
			
    8. 
						
  8. k8s测试容器test-for-k8s.yml
			
    9. 
						
  9. viewport的相关知识点
			
    10. 
						
  10. 数组翻转的方法（java实现）
			
    11.