link

6635 Nonsense Time

每次加入一个数字后求最长上升子序列长度

题目保证数据随机生成，就是说只有的概率会选到在最上上升子序列上的值，所以每次暴力跑，存下最长上升子序列的值就可以

#include <bits/stdc++.h>
#define sc scanf
#define pr printf
using namespace std;
int n, t;
int a[50005], b[50005];
bool vis[50005];
bool lis[50005];
int num[50005];
int ans;
int res[50005];

int c[50005];
int lowbit(int k)
{
    return k & (-k);
}
void update(int k, int x)
{
    while (k <= n)
    {
        c[k] = max(c[k], x);
        k += lowbit(k);
    }
}
int query(int k)
{
    int ans = 0;
    while (k)
    {
        ans = max(ans, c[k]);
        k -= lowbit(k);
    }
    return ans;
}

void find()
{
    ans = 0;
    memset(c, 0, sizeof(int) * (n + 1));
    for (int i = 1; i <= n; i++)
        lis[i] = false;
    for (int i = 1; i <= n; i++)
        num[i] = 0;
    for (int i = 1; i <= n; i++)
    {
        if (vis[i] == true)
            continue;
        int val = query(a[i] - 1) + 1;
        ans = max(ans, val);
        num[i] = val;
        update(a[i], val);
    }
    int val = ans;
    for (int i = n; i >= 1; i--)
    {
        if (num[i] == val)
        {
            lis[i] = true;
            val--;
            if (!val)
                break;
        }
    }
}
int main()
{
    int T;
    sc("%d", &T);
    while (T--)
    {
        sc("%d", &n);
        for (int i = 1; i <= n; i++)
        {
            vis[i] = false;
            sc("%d", &a[i]);
        }
        for (int i = 1; i <= n; i++)
            sc("%d", &b[i]);
        find();
        res[n] = ans;
        for (int i = n; i > 1; i--)
        {
            vis[b[i]] = true;
            if (lis[b[i]] == true)
                find();
            res[i - 1] = ans;
        }
        for (int i = 1; i <= n; i++)
            printf("%d%c", res[i], i == n ? '\n' : ' ');
    }
}

6638 Snowy Smile

区间最大子段和

https://blog.csdn.net/qq_41608020/article/details/98845958

6639 Faraway

给你n个士兵的xi,yi,ki,ti,满足题目中给出的方程
(|xi-xe|+|yi-ye|) mod ki=ti.
求有多少个(xe,ye)满足这n个方程

首先想到去绝对值,有绝对值肯定是不好算的.
n个士兵将平面分为了n^2个块
对于每一块内暴力计算.
由于k只能为2,3,4,5,所以只需要枚举每一块内的60个(其实可以更小)即可,
后面的和%60后的答案是一样的

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = 1e2+5;
ll n,m,x[MAX],y[MAX],k[MAX],t[MAX];
vector<ll> list1,list2;
bool check(ll X,ll Y){
    for(int i=1;i<=n;++i)
        if((abs(x[i]-X)+abs(y[i]-Y))%k[i]!=t[i])
            return false;
    return true;
}
ll calc(ll a,ll b){
    return (b-a-1)<0?0:(b-a-1)/60+1;
}
void solve(){
    int T;
    scanf("%d",&T);
    while(T--){
        list1.clear(); list2.clear();
        scanf("%lld%lld",&n,&m);
        list1.emplace_back(0);
        list1.emplace_back(m+1);
        list2.emplace_back(0);
        list2.emplace_back(m+1);
        for(int i=1;i<=n;++i){
            scanf("%lld%lld%lld%lld",&x[i],&y[i],&k[i],&t[i]);
            list1.emplace_back(x[i]);
            list2.emplace_back(y[i]);
        }
        sort(list1.begin(),list1.end());
        sort(list2.begin(),list2.end());
        ll ans=0;
        for(int i=0;i<list1.size()-1;++i)
            if(list1[i]<list1[i+1])
                for(int j=0;j<list2.size()-1;++j)
                    if(list2[j]<list2[j+1])
                        for(ll k1=0;k1<60;++k1)
                            for(ll k2=0;k2<60;++k2)
                                if(check(list1[i]+k1,list2[j]+k2))
        ans+=calc(list1[i]+k1,list1[i+1])*calc(list2[j]+k2,list2[j+1]);
        printf("%lld\n",ans);
    }
}
int main(void)
{
    solve();
    return 0;
}

6641 TDL

给两个数字 m，k，，已知 n 满足，其中是大于n的第m小的质数，例如 f(5,1)=6 and f(5,5)=11。求 n 的最小值

已知 m 的范围小于100，所以一定小于等于1000，所以枚举他的值，通过等式来算出 n 的值，再判断一下是否合法，合法就更新最小值，否则无解。

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 2005;
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
ll f(ll n, int m)
{
    for (ll i = n + 1; true; i++)
    {
        if (gcd(n, i) == 1)
        {
            m--;
            if (m == 0)
                return i;
        }
    }
}
int main()
{
    int T;
    sc("%d", &T);
    while (T--)
    {
        ll k;
        int m;
        sc("%lld%d", &k, &m);
        ll ans = 2e18;
        for (ll i = 0; i <= 1000; i++)
        {
            ll fn = i;
            ll n = k ^ i;
            if (n == 0)
                continue;
            if (f(n, m) - n == fn)
            {
                ans = min(ans, n);
            }
        }
        if (ans == 2e18)
            ans = -1;
        pr("%lld\n", ans);
    }
}

6645 Stay Real

签到，有 n 个结点的完全二叉树，每个点对应一个权值，每次只能取叶子结点，两个人在树上取数，求两个人取的数的大小。

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 2005;
bool vis[100005];
ll h[100005];
auto cmp = [](int q, int w) {
    return h[q] < h[w];
};
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int n;
        sc("%d", &n);
        for (int i = 1; i <= n; i++)
        {
            sc("%lld", &h[i]);
            vis[i] = false;
        }
        vis[n + 1] = true;
        priority_queue<int, vector<int>, decltype(cmp)>q(cmp);
        for (int i = n; i >= 1; i--)
            if (i * 2 > n)
                q.push(i);
        int op = 0;
        ll ans1 = 0, ans2 = 0;
        while (!q.empty())
        {
            int t = q.top();
            q.pop();
            vis[t] = true;
            int fa = t / 2;
            while (fa)
            {
                if (vis[2 * fa] == true && vis[2 * fa + 1] == true)
                {
                    q.push(fa);
                    fa /= 2;
                }
                else
                    break;
            }
            if (!op)
                ans1 += h[t];
            else
                ans2 += h[t];
            op ^= 1;
        }
        printf("%lld %lld\n", ans1, ans2);
    }
}

hdu 多校赛 第六场

slove 2/12

rank 358