一共补了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;
}