absi2011's Blog & Daily Life.

全新的开始       我要省选翻盘       I wanna AK in 高考\化学       自此,生无可恋
Topcoder 729(Div 1)
[破碎的状态] cf 101630A

[破碎的状态] Codeforces Round #467 补题记录

absi2011 posted @ Feb 26, 2018 07:08:01 PM in 刷题记录 with tags DP BFS 图论 CF Div.2 Div.1 瞎搞 小高考 , 620 阅读

一共补了5道题

题意:

Div 2-B

给你一个p一个y

求<=y的最大数x,使得x不是2~p中任何一个数的倍数

2<=p<=y<=1e9

Div 1-A

给三个数k,d,t(1<=k,d,t<=1e18)

你在烤一块鸡排,你的炉子很节能,当你按下开关的时候,它会连续工作k秒,然后断掉

你每d秒就会检查一次你的炉子,如果发现它关了就把它打开

你的鸡排需要总共t秒开着的炉子烤才能熟.当然,即使炉子被关掉了,它还能提供一些热量,假设你一直用关掉的炉子在烤,需要2t秒才能熟.

问:几秒后你的鸡排熟了

Div 1-B

两个人在做一个游戏

给你一个n个点m条边的有向图,一开始你在s,每次每人移动一步,动不了的人输;动了1e6次以上判和局

你的对手睡着了,你可以帮他执行操作

求你是否有胜利策略

有的话输出Win,然后输出方案(每次走哪)

没有的话,是否能平局,能的话Draw,不能的话Lose(这个没方案输出)

n<=1e5 m<=1e5

Div 1-C

给你两个字符串s和t

你现在只有一种操作

对于一个字符串,选择一个位置将其分成两部分a和b(a可以为0)

然后将b翻转得到b',将这个字符串再按照b'a的顺序接回来,得到新的字符串

例如"abcde"我们选择bc之间切

那么a="ab" b="cde" b'="edc" 所以字符串变为"edcab"

问是否能在6100次内由s得到t

能的话请构造方案

n<=2000

n为字符串长度

Div 1-D

真的不会表述题意...

你在玩一个游戏..前方有2*n的地区

你一开始控制一个坦克,这个坦克充能需要t秒,充能后可以开一炮,打掉当前这一行目前最前面的一个障碍物

你一开始在第一行的0号点,你要到第一行的n+1号点

你可以上下移动坦克,每次是瞬移

给你障碍物的位置,求你是否能到目的地

能的话输出方案

n<=1e9 障碍数<=1e6 t<=1e9

====================================

题解:

Div 2-B

从y往下枚举

如果到p就停,输出-1

如果找到确实不是2~p的倍数也停,输出答案(如果p比较大,这一步就是一个判质数)

找到的素数肯定是答案

根据素数的分布状况,那么这个枚举过程不会太长

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int n;
bool check(int x)
{
    int i;
    for (i=2;i*i<=x;i++)
    {
        if (i>n) break;
        if (x%i==0) return false;
    }
    return true;
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int y;
    cin>>n>>y;
    for (;;)
    {
        if (y==n) break;
        if (check(y))
        {
            printf("%d\n",y);
            return 0;
        }
        y--;
    }
    puts("-1");
    return 0;
}

Div 1-A

我们会发现,若干个d加起来大于等于k的时候,才为一次有效的开炉子

例如d=2 k=3那么和d=4 k=3等价

那么我们按d>=k来算

那么k秒2倍速 d-k秒1倍速

直接拿t除一下(d+k)再根据余数分析一下就好了

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    long long k,d,t;
    cin>>k>>d>>t;
    t*=2;
    long long val=d-k%d;
    if (val==d) val=0;
    //Every (k+val) min
    //2*k+val
    long long t2=t/(2*k+val);
    t%=(2*k+val);
    t2*=(k+val);
    if (t<=2*k)
    {
        t2+=t/2;
        cout<<t2<<".";
        if (t%2==0) cout<<"000"; else cout<<"500";
        cout<<endl;
    }
    else
    {
        t2+=k;
        t-=k*2;
        cout<<t2+t<<".000"<<endl;
    }
    return 0;
} 

Div 1-B

vis[i][0/1]表示 先手到这个点/后手到这个点 是否存在

那么我们只要找是否有vis[x][1]为真并且x没有后继了

那么可以处理好Win的情况

我们再dfs一次看有没有环

有环就Draw

再不行就Lose

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct edge
{
    int y;
    edge * next;
};
edge * new_edge()
{
    static edge a[200005];
    static int top=0;
    return &a[top++];
}
edge * li[100005];
void insert_edge(int x,int y)
{
    edge * t=new_edge();
    t->y=y;
    t->next=li[x];
    li[x]=t;
}
bool vis[100005][2];
int pre[100005][2];
void dfs(int x,int y)
{
    if (x==-1) return;
    dfs(pre[x][y],!y);
    printf("%d ",x+1);
}
bool bfs(int s)
{
    static int que[200005];
    int front=0,rail=1;
    que[0]=s*2;
    vis[s][0]=true;
    pre[s][0]=-1;
    for (;front<rail;front++)
    {
        int nowx=que[front]/2;
        int nowy=que[front]%2;
        edge * t;
        for (t=li[nowx];t!=0;t=t->next)
        {
            if (!vis[t->y][!nowy])
            {
                vis[t->y][!nowy]=true;
                pre[t->y][!nowy]=nowx;
                que[rail++]=(t->y)*2+(!nowy);
            }
        }
        if ((li[nowx]==0)&&(nowy==1))
        {
            puts("Win");
            dfs(nowx,nowy);
            return true;
        }
    }
    return false;
}
bool inque[100005];
bool vis2[100005];
bool dfs(int x)
{
    vis2[x]=true;
    inque[x]=true;
    edge * t;
    for (t=li[x];t!=0;t=t->next)
    {
        if (inque[t->y])
        {
            return true;
        }
        else if (vis2[t->y])
        {
            continue;
        }
        else
        {
            if (dfs(t->y))
            {
                return true;
            }
        }
    }
    inque[x]=false;
    return false;
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n,m;
    scanf("%d%d",&n,&m);
    int i;
    for (i=0;i<n;i++)
    {
        int s;
        scanf("%d",&s);
        int j;
        for (j=0;j<s;j++)
        {
            int x;
            scanf("%d",&x);
            x--;
            insert_edge(i,x);
        }
    }
    int s;
    scanf("%d",&s);
    s--;
    if (bfs(s)) return 0;
    if (dfs(s))
    {
        puts("Draw");
    }
    else
    {
        puts("Lose");
    }
    return 0;
} 

Div 1-C

我先写了个枚举

我们考虑,什么样的操作能把一个字符放到最前面而不干扰别的操作呢?

由题目的2000和6100可以感觉应该只有三次操作

枚举了下

"abcdef" --> "cxxxxx"

找到了一个到"cabxxx"的方式是这样

"abcdef" --> "fedcba" --> "abfedc" --> "cabfed"

实际上就是将后三个倒叙,前两个没变化

那么每次我们找一个,丢到前面就行了

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
bool check(string a,string b)
{
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    return a!=b;
}
vector<int> ans;
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    string s,t;
    int n;
    cin>>n;
    cin>>s>>t;
    if (check(s,t))
    {
        puts("-1");
        return 0;
    }
    n=s.length();
    int i;
    for (i=n-1;i>=0;i--)
    {
        int j;
        for (j=n-i-1;j<n;j++)
        {
            if (s[j]==t[i]) break;
        }
        ans.push_back(n);
        reverse(s.begin(),s.end());
        if (j!=0)
        {
            ans.push_back(j);
            string a=s.substr(0,n-j);
            string b=s.substr(n-j);
            reverse(b.begin(),b.end());
            s=b+a;
        }
        ans.push_back(1);
        string a=s.substr(0,n-1);
        string b=s.substr(n-1);
        reverse(b.begin(),b.end());
        s=b+a;
    }
    //cout<<s<<" "<<t<<endl;
    printf("%d\n",ans.size());
    for (i=0;i<ans.size();i++)
    {
        printf("%d ",ans[i]);
    }
    return 0;
} 

Div 1-D

我们考虑这样一个情况

如果我们能量满了,立刻轰击,等于我们继续积攒能量继续往前走

但是这样的话,一旦换路,就不等于了.因为换路以后你之前的轰击就等于打到别的上面了.

所以我们这么dp

dp(i,j)表示第j行第i列的时候能量为多少

转移的时候,我们考虑:从前面走过来,能量+1; 攻击前面的障碍物,能量-t

考虑从旁边走过来;能量=max(t,能量);如果旁边是障碍物或者这一格是障碍物都不能这么做

那么我们可以离散化一下,每个障碍物的位置和它前面一格的位置(因为可能要切换路线)

方案的话,有点麻烦,不过就是在dp的基础上记录一下路径,然后反推结论就是

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int x[1000005];
int y[1000005];
int z[2000005];
int dp[2000005][2];
int from[2000005][2];
vector<int> tt;
vector<pair<int,int> > shot;
void dfs(int n,int i)
{
    if ((n==0)&&(i==0)) return;
    int k=from[n][i];
    dfs(k/2,k%2);
    if (k/2==n)
    {
        if (n==0)
        {
            tt.push_back(0);
        }
        else
        {
            tt.push_back(z[n-1]);
        }
    }
    else
    {
        int t;
        if (k/2==0)
        {
            t=0;
        }
        else
        {
            t=z[k/2-1];
        }
        if (dp[n][i]-dp[k/2][k%2]!=z[n-1]-t)
        {
            shot.push_back(make_pair(z[n-1]-dp[n][i],i+1));
        }
    }
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n,m1,m2,t;
    scanf("%d%d%d%d",&n,&m1,&m2,&t);
    int i;
    int cnt=0;
    for (i=0;i<m1;i++)
    {
        scanf("%d",&x[i]);
        z[cnt++]=x[i];
        if (x[i]!=n) z[cnt++]=x[i]+1;
    }
    x[m1]=n+2;
    for (i=0;i<m2;i++)
    {
        scanf("%d",&y[i]);
        z[cnt++]=y[i];
        if (y[i]!=n) z[cnt++]=y[i]+1;
    }
    y[m2]=n+2;
    sort(z,z+cnt);
    cnt=unique(z,z+cnt)-z;
    dp[0][0]=0;
    dp[0][1]=0;
    from[0][1]=0;
    int nowi=0,nowj=0;
    int last=0;
    for (i=0;i<cnt;i++)
    {
        dp[i+1][0]=-1;
        dp[i+1][1]=-1;
        if (dp[i][0]>=0)
        {
            dp[i+1][0]=dp[i][0]+(z[i]-last);
            from[i+1][0]=i*2;
        }
        if (dp[i][1]>=0)
        {
            dp[i+1][1]=dp[i][1]+(z[i]-last);
            from[i+1][1]=i*2+1;
        }
        last=z[i];
        if (z[i]==x[nowi])
        {
            dp[i+1][0]-=t;
            if (dp[i+1][0]<=0) dp[i+1][0]=-1;
        }
        if (z[i]==y[nowj])
        {
            dp[i+1][1]-=t;
            if (dp[i+1][1]<=0) dp[i+1][1]=-1;
        }
        if (z[i]!=y[nowj])
        {
            if (min(dp[i+1][0],t)>dp[i+1][1])
            {
                dp[i+1][1]=min(dp[i+1][0],t);
                from[i+1][1]=i*2+2;
            }
        }
        if (z[i]!=x[nowi])
        {
            if (min(dp[i+1][1],t)>dp[i+1][0])
            {
                dp[i+1][0]=min(dp[i+1][1],t);
                from[i+1][0]=i*2+3;
            }
        }
        if (z[i]==x[nowi])
        {
            nowi++;
        }
        if (z[i]==y[nowj])
        {
            nowj++;
        }
    }
    if ((dp[cnt][0]<0)&&(dp[cnt][1]<0))
    {
        puts("No");
    }
    else
    {
        puts("Yes");
        if (dp[cnt][0]<0)
        {
            dfs(cnt,1);
            tt.push_back(n+1);
        }
        else
        {
            dfs(cnt,0);
        }
        printf("%d\n",tt.size());
        for (i=0;i<tt.size();i++)
        {
            printf("%d ",tt[i]);
        }
        printf("\n");
        printf("%d\n",shot.size());
        for (i=0;i<shot.size();i++)
        {
            printf("%d %d\n",shot[i].first,shot[i].second);
        }
    }
    return 0;
} 
HRMS Login 说:
Aug 02, 2022 04:45:09 PM

HRMS is termed as Human Resource Management System which is an important department for the welfare of an Organization, and any department that might be under surveillance of Government or Private organization, and HRMS is a combination of Process and system under Human resource Management & Information technology using HR software. A workplace can be well maintained under the working hands of an HRMS login which subdivides every system into different parts. HRMS Login It is all about automating the things making them available for all employees irrespective of workload. As every employee of an organization from top-level to bottom can access the HRMS software. It makes the financial department workload to reduce for maximum percentage.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter