Codeforces Round #614（Div.2）

A題：https://codeforces.com/contest/1293/problem/A

題意：有一個食堂，共n層，但是有k層關閉了，現在A在第s層，問A至少爬幾層樓梯可以吃飯。

思路：這道題的話，用set做一下就行。

AC代碼：

#include <bits/stdc++.h>
typedef long long ll;
const int maxx=10010;
const int inf=0x3f3f3f3f;
using namespace std;
int main()
{
    int t;
    cin>>t;
    set<int>st;
    while(t--)
    {
        st.clear();
        int n,s,k;
        cin>>n>>s>>k;
        while(k--)
        {
            int a;
            cin>>a;
            st.insert(a);
        }
        int ans=0;
        while((st.count(s+ans) || s+ans>n) && (st.count(s-ans) || s-ans<=0))
            ans++;
        cout<<ans<<endl;
    }
    return 0;
}
           

B題：https://codeforces.com/contest/1293/problem/B

題意：J有s個對手，每個問題可以有t個人回答錯誤，他便可獲得t/s的收益，問J的最大收益是多少。

思路：這道題的話，貪心，每次淘汰一人賺的更多。

AC代碼：

#include <bits/stdc++.h>
typedef long long ll;
const int maxx=10010;
const int inf=0x3f3f3f3f;
using namespace std;
int main()
{
    int n;
    cin>>n;
    double ans=0;
    for(int i=1; i<=n; i++)
        ans+=1.0/(double)i;
    cout<<fixed<<setprecision(12)<<ans<<endl;
    return 0;
}
           

C題：https://codeforces.com/contest/1293/problem/C

題意：有一個2*n的矩陣，初始時每一個矩陣中每一個方格都是可通過的，然後有q個詢問，每次給出一個方格的坐标，使得這個方格的狀态翻轉（通過變不通過或者不通過變通過），對于每個查詢問你是否可以從（1,1）到(2,n)。

思路：這道題的話，每個岩漿點的對面或斜對面如果也有岩漿點，那麼這兩點之間就會形成障礙，統計這種障礙的數量即可。

AC代碼：

#include <bits/stdc++.h>
typedef long long ll;
const int maxx=100010;
const int inf=0x3f3f3f3f;
using namespace std;
int a[5][maxx];
int n,q,k,x,y;
int main()
{
    cin>>n>>q;
    while(q--)
    {
        cin>>x>>y;
        x--;
        if(a[x][y]==0)
        {
            a[x][y]=1;
            for(int i=-1; i<=1; i++)
            {
                if(a[1-x][y+i]==1)
                    k++;
            }
        }
        else
        {
            a[x][y]=0;
            for(int i=-1; i<=1; i++)
            {
                if(a[1-x][y+i]==1)
                    k--;
            }
        }
        if(!k)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
    return 0;
}
           

D題：https://codeforces.com/contest/1293/problem/D

題意：給定x0,y0,ax,ay,bx,by，一堆資料點：(x0,y0)，(x1,y1) = (ax* x0+bx,ay*y0+by），起點（xs,ys），時間t，走一步都需要1機關時間，t時間内，從起點出發最多可以收集多少個資料點。

思路：這道題的話，分析點集的特點，可以知道每一個資料點都在下标比它小的資料點的右上方，而且離下一個資料點的距離大于離第0個資料點的距離。枚舉Aroma從哪個點出發；先往第0個資料點走，然後盡可能往右上走。

AC代碼：

#include <bits/stdc++.h>
typedef long long ll;
const int maxx=100010;
const int inf=0x3f3f3f3f;
using namespace std;
ll a0, b0, ax, bx, ay, by;
ll xs, ys, t;
ll dx[maxx], dy[maxx];
ll dis[maxx];
int res;
int main()
{
    cin>>a0>>b0>>ax>>ay>>bx>>by;
    cin>>xs>>ys>>t;
    ll tx=a0, ty=b0;
    int top;
    for(top=0; tx<=2e16 && ty<=2e16; top++)
    {
        dx[top]=tx;
        dy[top]=ty;
        tx=tx*ax+bx;
        ty=ty*ay+by;
    }
    for(int i=1; i<=top-1; i++)
        dis[i]=dx[i]-dx[0]+dy[i]-dy[0];
    for(int i=0; i<=top-1; i++)
    {
        ll tmp=t-abs(xs-dx[i])-abs(ys-dy[i]);
        if (tmp<0)
            continue;
        int tot=0;
        if (tmp<=dis[i])
        {
            tot=i-(lower_bound(dis,dis+top,dis[i]-tmp)-dis)+1;
        }
        else
        {
            tot=upper_bound(dis+i+1,dis+top,tmp-dis[i])-dis;
        }
        res=max(res,tot);
    }
    cout<<res<<endl;
}