week1

2021-08-01

第一周

外星人的侵略策略（东大oj）

链接：

https://f-oj.neu.edu.cn/contest/10/problem/9

思路：

需要比较两个数的阶乘后四位Σ(⊙▽⊙”a… ，20！就已经顶到了long long的最深处了，但这小破题明显不是在考高精。所以就要从为题出发了，不难发现，20！以后的后四位都是0000，那么答案就很明显了，20！以后的hxd们都会白给，只要吧19！以前打个表就完了，是这样了。

俺是一坨垃圾代码QWQ:

int main()
{
    ios::sync_with_stdio(0);
    int sss[20] = {1, 2, 6, 24, 120, 720, 5040, 320, 2880, 8800, 6800, 1600, 800, 1200, 8000, 8000, 6000, 8000, 2000};
    ll b, n;
    while(cin>>b>>n)
    {
        if(b>20)
        b = 0;
    else
        b = sss[b - 1];
    int flag = 0;
    for (int i = 0; i < n;i++)
    {
        ll x;
        cin >> x;
        if(x<=19)
        {
            if(sss[x-1]>b)
                {
                    flag = 1;
                }
        }
    }
    if(!flag)
            cout << "dou shi zhan dou li wu." << endl;
        else
        cout << "yao kuai dian tao zou!!!!" << endl;
    }
    
    return 0;
}

未曾设想的标题（东大oj）

链接：

https://f-oj.neu.edu.cn/contest/10/problem/8

思路：

一道规律题（怎么有点像约瑟夫环），判断是否是“kltxdy”好说，问题是到k轮后dy应该数到几。从i开始就是第一轮，到第k轮时，i数到(k - 1) * n+x。如果i<=j,则j在i右面（j-i）的位置上，如果i>j,则到j需要再进行一轮，此时j在i左面，减去差值即可。

俺是一坨垃圾代码QWQ:

bool judge(int x)
{
    while(x)
    {
        if(x%10==7)
            return 1;
        x /= 10;
    }
    return 0;
}
int main()
{
    int t;
    cin>>t;
    int n, x;
    while(t--)
    {
        cin >> n >> x;
        int i, j, k;
        cin >> i >> j >> k;
        int res = (k - 1) * n+x;
        if(i<=j)
            res += j - i;
        else
            res += j+n-i;
            
        if(judge(res)||res%7==0)
            cout << "kltxdy" << endl;
        else
            cout << res<<endl;
    }

}

Find The Array（cf）

链接：

https://codeforces.com/contest/1550/problem/A

思路：

贪心，从1开始，以2为公差往上贪心，直到前n项和大于等于目标值，则n为答案。
等差数列前n项和为n^2，当n^2大于等于目标值，n为答案。tips:为了简化计算，可以直接对目标值开方，若能开出整次方，则mid为答案，若开不出整次方则mid+1为答案。

俺是一坨垃圾代码QWQ:

int main()
{
    int t;
    cin>>t;
    for (int i = 0; i < t;i++)
    {
        int x,mid;
        cin >> x;
        mid = sqrt(x);
        if(mid*mid!=x)
        {
            cout << mid+1<<endl;
        }
        else
            cout << mid<<endl;
    }
}

Maximum Cost Deletion（cf）

链接：

https://codeforces.com/contest/1550/problem/B

思路：

由给出的公式可知，不管怎么删除，得分都有固定的a*n，因此问题就在于对于b的讨论，当b>=0时，一个一个删除得分最多。b<0时，将分出的块数+1,就是最少的删除数量*b+a*n就是答案Σ(⊙▽⊙”a…

俺是一坨垃圾代码QWQ:

int main()
{
    int t;
    int n, a, b;
    string str;
    cin>>t;
    for (int i = 0; i < t;i++)
    {
        cin >> n >> a >> b;
        cin >> str;
        if(b>=0)
            cout << (a + b) * n<<endl;
        else
        {
            int n2 = 1;
            for (int i = 1; i < str.size();i++)
            {
                if(str[i]!=str[i-1])
                    n2++;
            }
            cout << a * n + b * (n2 / 2 + 1) << endl;
        }
    }
}

Strange Table（cf）

链接：

https://codeforces.com/contest/1506/problem/A

思路：

行转列，列转行问题。注意在被整除的情况就可以了。

俺是一坨垃圾代码QWQ:

int main()
{
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while(t--)
    {
        ll n, m, x;
        cin >> n >> m >> x;
        int a, b;
        a = x%n==0?x / n : x / n + 1;//lie 3
        b = x % n==0?n:x%n;//hang 2
        cout << m * (b-1) + a<<endl;
    }
    return 0;
}

Partial_Replacement（cf）

链接：

https://codeforces.com/contest/1506/problem/B

思路：

贪心，从第一个*开始贪，每次都以最大长度s来贪，贪出来的话就更新i，贪不出来就直接退出循环，输出结果

俺是一坨垃圾代码QWQ:

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int n, s,ans=0,i,j=0;
        cin >> n >> s;
        string str;
        cin >> str;
        i = str.find_first_of('*');
        while(1)
        {
            j= min(n - i, s);
            for (; j >= 0;j--)
            {
            if(str[i+j]=='*')
                break;
            }
            i += j;
            ans++;
            if(j==0)
                break;
        }
        cout << ans << endl;
    }
}

H - LIS（AT2827）

链接

https://atcoder.jp/contests/chokudai_s001/tasks/chokudai_S001_h

思路：

整一道Lis板子题，朴素的双for写法是dp数组里存放某位置下最大子序列长度，转移方程：f[i]=f[j]+1;
二分优化：dp数组存放能构成递增序列的最小元素，利用lower_bound查找大于等于当前值的dp数组进行替换。转移方程长度为答案

俺是一坨垃圾代码QWQ:

int main()
{
    int n,res=0;
    cin >> n;
    vector<int> nums(n + 1, 0);
    vector<int> dp(n + 1, 0);
    for (int i = 0; i < n;i++)
        cin >> nums[i];
    dp[1] = nums[0];
    int len = 1;
    for (int i = 0; i < n;i++)
    {
        if(nums[i]>dp[len])
            dp[++len] = nums[i];
        else
        {
            int j = lower_bound(dp.begin() + 1, dp.begin() + len + 1, nums[i]) - dp.begin();
            dp[j] = nums[i];
        }
    }
    cout << len << endl;
}