首页 > 其他分享 >HIAST Collegiate Programming Contest 2024（非完全题解）

HIAST Collegiate Programming Contest 2024（非完全题解）

时间：2024-10-16 22:21:46浏览次数：1  
标签：tmp typedef Contest int 题解 ll Programming vx inline

C题HZY做的，等他补题解

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// //如果在不支持 avx2 的平台上将 avx2 换成 avx 或 SSE 之一
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
vector<int> vx;
inline void divide() {sort(vx.begin(),vx.end());vx.erase(unique(vx.begin(),vx.end()),vx.end());}
// inline int mp(int x) {return upper_bound(vx.begin(),vx.end(),x)-vx.begin();}
inline int log_2(int x) {return 31-__builtin_clz(x);}
inline int popcount(int x) {return __builtin_popcount(x);}
inline int lowbit(int x) {return x&-x;}
inline ll Lsqrt(ll x) { ll L = 1,R = 2e9;while(L + 1 < R){ll M = (L+R)/2;if(M*M <= x) L = M;else R = M;}return L;}
#define N 100005
int f[25][N];
int Log2[N];
int n,a[N];
int query(int l,int r)
{
    int k = Log2[r-l+1];
    return f[k][l] & f[k][r-(1<<k)+1];
}

void solve()
{
    cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i], f[0][i]=a[i];
    for(int j=1;j<=Log2[n];++j)
    {
        for(int i=1;i+(1<<j-1)<=n;++i)
        {
            f[j][i] = (f[j-1][i] & f[j-1][i+(1<<j-1)]);
        }
    }

    for(int i=1;i<=n;++i)
    {
        int l,r,mid;
        int L,R;
        l=1; r=i;
        while(l<r)
        {
            mid = (l+r)>>1;
            if(query(mid, i) == a[i]) r=mid;
            else l=mid+1;
        }
        L=l;
        l=i, r=n;
        while(l<r)
        {
            mid = (l+r+1)>>1;
            if(query(i, mid) == a[i]) l=mid;
            else r=mid-1;
        }
        R=l;
        cout<<(ll)(R-i+1)*(i-L+1)<<' ';
    }
    cout<<'\n';
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
    Log2[0]=-1;
    for(int i=1;i<N;++i) Log2[i] = Log2[i/2]+1;
	int T;
	cin>>T;
	while(T--)
	{
		solve();
	}
}

H（博弈）

\(zhuge开的，关注到不管是移动一个还是三个都会改变sum的奇偶性\)

    // #pragma GCC optimize("O3,unroll-loops")
    // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
    // //如果在不支持 avx2 的平台上将 avx2 换成 avx 或 SSE 之一
    #include<bits/stdc++.h>
    using namespace std;
    #define x first
    #define y second
    typedef pair<int,int> PII;
    typedef long long ll;
    typedef unsigned long long ull;
    typedef unsigned int uint;
    typedef vector<string> VS;
    typedef vector<int> VI;
    typedef vector<vector<int>> VVI;
    vector<int> vx;
    inline void divide() {sort(vx.begin(),vx.end());vx.erase(unique(vx.begin(),vx.end()),vx.end());}
    inline int mp(int x) {return upper_bound(vx.begin(),vx.end(),x)-vx.begin();}
    inline int log_2(int x) {return 31-__builtin_clz(x);}
    inline int popcount(int x) {return __builtin_popcount(x);}
    inline int lowbit(int x) {return x&-x;}
    inline ll Lsqrt(ll x) { ll L = 1,R = 2e9;while(L + 1 < R){ll M = (L+R)/2;if(M*M <= x) L = M;else R = M;}return L;}
    void solve()
    {
        int n;
        cin>>n;
        int a;
        ll sum = 0;
        for(int i=0;i<n;++i)
        {
            cin>>a;
            sum += a;
        }
        cout<<((sum&1)?("YES\n"):("NO\n"));
    }
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        int T;
        cin>>T;
        while(T--)
        {
            solve();
        }
    }

I（纯签到）

\(注意find函数若没找到是!=npos没有括号\)

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//如果在不支持 avx2 的平台上将 avx2 换成 avx 或 SSE 之一
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
vector<int> vx;
inline void divide() {sort(vx.begin(),vx.end());vx.erase(unique(vx.begin(),vx.end()),vx.end());}
// inline int mp(int x) {return upper_bound(vx.begin(),vx.end(),x)-vx.begin();}
inline int log_2(int x) {return 31-__builtin_clz(x);}
inline int popcount(int x) {return __builtin_popcount(x);}
inline int lowbit(int x) {return x&-x;}
inline ll Lsqrt(ll x) { ll L = 1,R = 2e9;while(L + 1 < R){ll M = (L+R)/2;if(M*M <= x) L = M;else R = M;}return L;}
void solve()
{
    string s;
    cin>>s;
    string std = "bitset";
    if(s.find(std) != s.npos)
    {
        cout<<"7as\n";
    }
    else
    {
        cout<<"no 7as for you today\n";
    }
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T;
	cin>>T;
	while(T--)
	{
		solve();
	}
}

K题HZY做的，等他补题解

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//如果在不支持 avx2 的平台上将 avx2 换成 avx 或 SSE 之一
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
vector<int> vx;
inline void divide() {sort(vx.begin(),vx.end());vx.erase(unique(vx.begin(),vx.end()),vx.end());}
inline int mp(int x) {return upper_bound(vx.begin(),vx.end(),x)-vx.begin();}
inline int log_2(int x) {return 31-__builtin_clz(x);}
inline int popcount(int x) {return __builtin_popcount(x);}
inline int lowbit(int x) {return x&-x;}
inline ll Lsqrt(ll x) { ll L = 1,R = 2e9;while(L + 1 < R){ll M = (L+R)/2;if(M*M <= x) L = M;else R = M;}return L;}

#define N 100005
int n,q;
vector<int> e[N];
vector<int> edfn[N];
int fa[N], siz[N], dep[N], son[N], top[N];
int dfn[N];
int tot;
void dfs_init(int u)
{
    siz[u] = 1;
    son[u] = 0;
    dfn[u] = ++tot;
    for(auto &&v:e[u])
    {
        dep[v] = dep[u] + 1;
        dfs_init(v); 
        siz[u] += siz[v];
        if(siz[v] > siz[son[u]]) son[u] = v;
    }

    edfn[u].resize(e[u].size());
    for(int i=0;i<e[u].size();++i)
    {
        edfn[u][i] = dfn[e[u][i]];
    }
}
void dfs_shupou(int u,int topx)
{
    top[u] = topx;
    if(son[u]) dfs_shupou(son[u], topx);
    for(auto &&v:e[u])
    {
        if(v==son[u]) continue;
        dfs_shupou(v, v);
    }
}
int lca(int x,int y)
{
    while(top[x] != top[y])
    {
        if(dep[top[x]] < dep[top[y]]) swap(x,y);
        x = fa[top[x]];
    }
    if(dep[x] < dep[y]) return x;
    else return y;
}

void solve()
{
    cin>>n>>q;
    tot = 0;
    for(int i=1;i<=n;++i) e[i].clear(), edfn[i].clear();
    for(int i=2;i<=n;++i)
    {
        cin>>fa[i];
        e[fa[i]].push_back(i);
    }
    for(int i=1;i<=n;++i) sort(e[i].begin(),e[i].end());
    dep[1]=0;
    dfs_init(1);
    dfs_shupou(1,1);

    while(q--)
    {
        int v,x,u; cin>>v>>x>>u;
        auto f = [&](int y){cout<<(x>=y?"YES\n":"NO\n");};
        if(u==v) {f(1); continue;}
        
        int r = lca(v,u);
        // int fu = e[r][upper_bound(edfn[r].begin(), edfn[r].end(), dfn[u])-1-edfn[r].begin()];
        if(dfn[u] < dfn[v])
        {
            int fv = e[r][upper_bound(edfn[r].begin(), edfn[r].end(), dfn[v])-1-edfn[r].begin()];
            f(dfn[u]-dfn[r]+1 + siz[fv]);
        }
        else
        {
            f(dfn[u]-dfn[r]+1);
        }
    }
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T;
	cin>>T;
	while(T--)
	{
		solve();
	}
}

H题（简单构造）

\(当x为10次幂时显然无解，否则为离他最近的10次幂\)

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//如果在不支持 avx2 的平台上将 avx2 换成 avx 或 SSE 之一
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
vector<int> vx;
inline void divide() {sort(vx.begin(),vx.end());vx.erase(unique(vx.begin(),vx.end()),vx.end());}
inline int mp(int x) {return upper_bound(vx.begin(),vx.end(),x)-vx.begin();}
inline int log_2(int x) {return 31-__builtin_clz(x);}
inline int popcount(int x) {return __builtin_popcount(x);}
inline int lowbit(int x) {return x&-x;}
inline ll Lsqrt(ll x) { ll L = 1,R = 2e9;while(L + 1 < R){ll M = (L+R)/2;if(M*M <= x) L = M;else R = M;}return L;}
set<ll> P;
void solve()
{
    ll x;
    cin>>x;
    ll inf = 1e18;
    if(P.find(x)!=P.end()) cout<<"-1\n";
    else 
    {
        auto it = P.lower_bound(x);
        cout<<*it<<'\n';
    }
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
    ll tmp = 1;
    P.insert(1);
    for(int i=1;i<=18;++i) {tmp = 10*tmp;P.insert(tmp);}
	int T;
	cin>>T;
	while(T--)
	{
		solve();
	}
}

D（数学+guess）

\(推到出满足关系的a_i, a_j有a_i = k\times p^3, a_j = k\times q^3，具有相同的k可以构成合法对，然后从大到小枚举p防止k算重复\)
数学推导等zhuge0来补


#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
vector<int> vx;
inline void divide() {sort(vx.begin(),vx.end());vx.erase(unique(vx.begin(),vx.end()),vx.end());}
// inline int mp(int x) {return upper_bound(vx.begin(),vx.end(),x)-vx.begin();}
inline int log_2(int x) {return 31-__builtin_clz(x);}
inline int popcount(int x) {return __builtin_popcount(x);}
inline int lowbit(int x) {return x&-x;}
inline ll Lsqrt(ll x) { ll L = 1,R = 2e9;while(L + 1 < R){ll M = (L+R)/2;if(M*M <= x) L = M;else R = M;}return L;}

#define N 50005
int n, x;
unordered_map<int,int> mp;
void solve()
{
    cin>>n;
    mp.clear();
    ll ans = 0;
    for(int i=1;i<=n;++i)
    {
        cin>>x;
        int p = pow(x,1.0/3);
        p ++;
        for( ;p ; --p)
        {
            int p3 = p*p*p;
            if(x % p3) continue;
            ans += mp[x / p3];
            ++mp[x / p3];
            break;
        }
    }
    cout<<ans<<'\n';

}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T;
	cin>>T;
	while(T--)
	{
		solve();
	}
}

J（找规律）

\(显然考虑重合边当且仅当为中线，否则对于与X轴垂直坐标为x来说寻找Y轴坐标为x或A-x（排除四等分），或者是X轴为2\times x，A-x，Y轴同理\)

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//如果在不支持 avx2 的平台上将 avx2 换成 avx 或 SSE 之一
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
vector<int> vx;
inline void divide() {sort(vx.begin(),vx.end());vx.erase(unique(vx.begin(),vx.end()),vx.end());}
inline int mp(int x) {return upper_bound(vx.begin(),vx.end(),x)-vx.begin();}
inline int log_2(int x) {return 31-__builtin_clz(x);}
inline int popcount(int x) {return __builtin_popcount(x);}
inline int lowbit(int x) {return x&-x;}
inline ll Lsqrt(ll x) { ll L = 1,R = 2e9;while(L + 1 < R){ll M = (L+R)/2;if(M*M <= x) L = M;else R = M;}return L;}

int n;
map<int,int> mpx,mpy;

void solve()
{
    cin>>n;
    int xs,ys,xe,ye;
    cin>>xs>>ys>>xe>>ye;
    int A = xe-xs;
    bool ok=false;
    for(int i=1;i<=n;++i)
    {
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        x1-=xs; y1-=ys;
        x2-=xs; y2-=ys;
        if(x1==x2) 
        {
            if(x1*2==A && mpx.find(x1) != mpx.end()) 
            {
                cout<<mpx[x1]<<' '<<i<<'\n';
                ok = true;
                break; 
            }
            mpx[x1]=i;
        }
        else if(y1==y2) 
        {
            if(y1*2==A && mpy.find(y1) != mpy.end()) 
            {
                cout<<mpy[y1]<<' '<<i<<'\n';
                ok = true;
                break; 
            }
            mpy[y1]=i;
        }
    }
    if(ok) return;
    for(auto &&[x,i]:mpx)
    {
        if(2*x == A) continue;
        if(mpy.find(x) != mpy.end()) {cout<<i<<' '<<mpy[x]<<'\n'; return;}
        if(mpy.find(A-x) != mpy.end()) {cout<<i<<' '<<mpy[A-x]<<'\n'; return;}
        if(mpx.find(2*x) != mpx.end() && 3*x != A) {cout<<i<<' '<<mpx[2*x]<<'\n'; return;}
        if(mpx.find(A-x) != mpx.end() && 3*x != A) {cout<<i<<' '<<mpx[A-x]<<'\n'; return;}
    }
    for(auto &&[y,i]:mpy)
    {
        if(2*y == A) continue;
        if(mpy.find(2*y) != mpy.end() && 3*y != A) {cout<<i<<' '<<mpy[2*y]<<'\n'; return;}
        if(mpy.find(A-y) != mpy.end() && 3*y != A) {cout<<i<<' '<<mpy[A-y]<<'\n'; return;}
    }
    cout<<"-1 -1\n";
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T=1;
	// cin>>T;
	while(T--)
	{
		solve();
	}
}

L（不好想的构造）

\(奇数没有，偶数可以，直接贴图，借鉴自O_start\)

class Node:
    def __init__(self, x, y):
        self.x = x
        self.y = y

def solve():
    t = int(input())  # 读取测试用例的数量
    for _ in range(t):
        n = int(input())  # 读取每个测试用例的多边形顶点数
        
        # 如果 n 是奇数，直接输出 -1
        if n % 2 != 0:
            print("-1")
        else:
            # 如果 n == 4，直接输出正方形的坐标
            if n == 4:
                print(f"0 0")
                print(f"0 1")
                print(f"1 1")
                print(f"1 0")
            else:
                # 如果 n 是 4 的倍数
                if n % 4 == 0:
                    tmp = Node(0, 0)
                    print(f"{tmp.x} {tmp.y}")
                    tmp.x += 2
                    tmp.y -= 1
                    print(f"{tmp.x} {tmp.y}")
                    for i in range(2, n // 2):
                        if i % 2 != 0:
                            tmp.x += 1
                            tmp.y -= 2
                        else:
                            tmp.x -= 1
                            tmp.y -= 2
                        print(f"{tmp.x} {tmp.y}")
                    
                    tmp.x -= 2
                    tmp.y += 1
                    print(f"{tmp.x} {tmp.y}")
                    
                    tmp.x -= 2
                    tmp.y -= 1
                    print(f"{tmp.x} {tmp.y}")
                    
                    for i in range(2, n // 2):
                        if i % 2 != 0:
                            tmp.x += 1
                            tmp.y += 2
                        else:
                            tmp.x -= 1
                            tmp.y += 2
                        print(f"{tmp.x} {tmp.y}")
                # 如果 n 不是 4 的倍数但仍为偶数
                else:
                    tmp = Node(0, 0)
                    print(f"{tmp.x} {tmp.y}")
                    for i in range(1, n // 2):
                        if i % 2 != 0:
                            tmp.x -= 1
                            tmp.y -= 2
                        else:
                            tmp.x += 1
                            tmp.y -= 2
                        print(f"{tmp.x} {tmp.y}")
                    
                    tmp.x -= 2
                    tmp.y -= 1
                    print(f"{tmp.x} {tmp.y}")
                    
                    for i in range(1, n // 2):
                        if i % 2 != 0:
                            tmp.x -= 1
                            tmp.y += 2
                        else:
                            tmp.x += 1
                            tmp.y += 2
                        print(f"{tmp.x} {tmp.y}")

# 调用解决函数
solve()

标签：tmp,typedef,Contest,int,题解,ll,Programming,vx,inline
From： https://www.cnblogs.com/DPPTSD/p/18471058

相关文章

  • HNCPC2024 2024湖南省赛 题解
    目录写在前面I签到C签到E二进制，枚举，子集DPK转化，分层图最短路A枚举，DP，简单计算几何J单调性，枚举，数据结构HDP，字符串，KMPD莫比乌斯反演，枚举写在最后写在前面比赛地址：https://codeforces.com/gym/105423。以下按个人难度向排序。利益相关：现场赛Au。没有和去年一样整场犯唐......
  • [题解]NOIP2018模拟赛 plutotree
    题目描述给定一棵有\(n\)个节点的树，根节点为\(1\)，节点\(i\)有权值\(w[i]\)。这棵树非常奇怪，它的每个叶子结点都有一条连向根节点的权值为\(0\)的边。给定\(q\)次询问，每次给定\(u,v\)，请计算出一条\(u\)到\(v\)的路径（每条边最多经过\(1\)次），最小化该路径上的点权之和，并在其基础上最......
  • P10353 [PA2024] Grupa permutacji 题解
    神秘！在这些排列生成的置换群\(G\)里，若\(\exists\pi\inG\)使得\(\pi_i=k,\pi_j=l\)，则所有这些\((k,l)\)被同样数量的\(\pi\inG\)通过前述方法得出。证明：设\(\pi(i,j)=(k,l),\pi'(i,j)=(k',l')\)（意义前述），则\(\pi^{-1}\circ\pi'(k,l)=(k',l')......
  • [题解]P3952 [NOIP2017 提高组] 时间复杂度
    P3952[NOIP2017提高组]时间复杂度我们把循环的嵌套关系看做树形结构，梳理一下\(3\)种情况：直接跳过当前子树：\(x,y\in\mathbb{N}\)，且\(x>y\)。\(x=\tt{"n"},y\in\mathbb{N}\)。不跳过，并在处理完所有子节点后追加\(n\)的时间复杂度：\(x\in\mathbb{N},y=\tt{"n"}\)。......
  • 【题解】[2023 合肥蜀山初中] 旅行(travel)
    题目传送门题目大意有一个\(n\)个点\(m\)条边的有向图组成的城市，每条边可以是骑行边或公共交通边，公共交通边只能走一条，边是从\(u_i\)到\(v_i\)的有向边，需要花费\(time_i\)的时间，求\(1\)到其他点的最短路径。思路分析有一个很巧妙的思路叫分层图，它的思路是因为只能......
  • Excel DLL丢失？Excel DLL文件下载指南及常见问题解决方案
    当您在使用MicrosoftExcel时遇到提示DLL文件丢失或损坏的情况，这可能会影响软件的正常运行。为了帮助您解决这一问题，本文提供了ExcelDLL文件的下载指南，并针对常见问题给出了解决方案。一、ExcelDLL文件下载指南确定缺失的DLL文件：首先，您需要确定是哪个DLL文件丢失或损坏......
  • 数据结构1系列题解前瞻
    A.线段树分裂算法：线段树、（平衡树？）板子题，不多做评价。但是开发空间很大，我的写法在洛谷题解上没找到，导致当时想贺题解没贺成。B.三元上升子序列算法：线段树、树状数组、分块、（CDQ分治？）二维偏序板子，开发空间极大，想怎么写就怎么写。C.STEP算法：线段树、分块线段树维护子区间信......
  • P1941 NOIP2014 提高组 飞扬的小鸟 题解
    P1941NOIP2014提高组飞扬的小鸟分析背包经典演变问题玩得挺花。设\(f[i][j]\)表示到达\((i,j)\)的时候的最小点击次数。题目中对于每一个\(i\)有两种处理：点击与不点击（重点：点击可以叠加）。所以，对于点击，我们可以像完全背包一样转移，而不点击就按照01背包转移。对于管......
  • [NOI2020] 美食家 题解
    属于是将矩阵快速幂的绝大部分技巧用到了极致的一道题。暴力部分首先我们先考虑一个普通DP。定义\(dp_{t,i}\)表示在时间为\(t\)时到达点\(i\)可以得到的愉悦值之和的最大值。显然有\((i,j)\inE\todp_{t+w,j}=\max(dp_{t,i}+c_j)\)。特判一下当前节点有美食节的情......
  • 洛谷 P5175 数列 题解
    纯纯数学题。看到\(n\le10^{18}\)不难想到矩乘，但是\(\log_210^{18}\approx60\)，再加上\(T=30000\)的多测，运算量已经来到了\(1.8\times10^6\)，所以我们最多有一个\(\sqrt[3]{\frac{1.5\times10^8}{6\times10^6}}\approx4\)的矩阵。\[\becausea_i=xa_{i-1}+ya_{......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99