小雷神奇的电脑

分析

二进制思维题

首先为了避免超时，可以想到是相邻之间运算，而异或是同或的反运算，所以求同或最大值可以用（还不是很懂，先放放）

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int,int>P;
const int N=2e5+10;
int n,m;
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    vector<int>a(32);
    a[0]=1;
    int cnt=1;
    for(int i=1;i<=30;i++)
    {
      cnt*=2;
      a[i]=a[i-1]+cnt;
    }
    vector<int>s(n);
    for(int i=0;i<n;i++)cin>>s[i];
    sort(s.begin(),s.end());
    int ma=2e9;//值定的大一点
    for(int i=0;i<n-1;i++)
    {
    ma=min(ma,s[i]^s[i+1]);
    }
    cout<<a[m-1]-ma;
    return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    vector<int>a(n);
    for(auto &x:a)cin>>x;
    sort(a.begin(),a.end());
    int ma=(1<<m)-1;
    int ans=0;
    for(int i=0;i<n-1;i++)ans=max(ans,a[i]^a[i+1]^ma);
    cout<<ans;
    return 0;
}

马拉松

树的遍历 求子树大小

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=3e5+10;
typedef pair<int,int>P;
int n,x,y,s[N];
vector<int>g[N];
bool st[N],check[N];
int dfs(int u)
{
    st[u]=1;
    s[u]=1;
    if(u==x)check[u]=1;
    for(int i:g[u])
    {
        if(!st[i])
        {
            s[u]+=dfs(i);
            check[u]|=check[i];
        }
    }
    return s[u];
}
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>x>>y;
    int m=n-1;
    while(m--)
    {
     int a,b;
     cin>>a>>b;
     g[a].push_back(b);
     g[b].push_back(a);
    }
    int tmp=dfs(y);
    int f=0;
    for(int i:g[y])
        if(check[i]==1)
            f=s[y]-s[i];
    int ans=f*s[x];
    cout<<ans;
    return 0;
}

岗位分配

组合数学 隔板法
也可用dp来解

#include<bits/stdc++.h>
#define int long long 
#define endl '\n'
using namespace std;
const int M=998244353,N=1e5+10;
int n,m,a[N];
int work(int x)
{
    return (x%M+M)%M;
} 
int qmi(int a,int b,int p)
{
int res=1;
a%=p;
while(b>0)
{
if(b&1)res=res*a%p;
a=a*a%p;
b>>=1;  
}   
return res;
}
int pmi(int a,int p)
{
    return qmi(a,p-2,p);
}
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    int sum=0;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        sum+=a[i];
    }
    if(sum>m)
    {
        cout<<0<<endl;
        return 0;
    }
    int ret=0;
    for(int p=0;p<=m-sum;p++)
    {
        int ans=1;
        for(int i=1;i<p+n;i++)
        ans=ans*i%M;
        for(int i=1;i<n;i++)
        ans=ans*pmi(i,M)%M;
        for(int i=1;i<=p;i++)
        ans=ans*pmi(i,M)%M;
        ret=(ret+ans)%M;
    }
    cout<<ret;
    return 0;
}

#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define sz(x) (int)((x).size())
#define int ll
using namespace std;
const int N=100005;
int n,m,dp[N],a[N],s[N];
void BellaKira()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++)
        cin>>a[i],m-=a[i];
    dp[0]=1;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++) dp[j]=(dp[j-1]+dp[j])%mod;
    }
    int ans=0;
    for (int j=0;j<=m;j++) ans=(ans+dp[j])%mod;
    cout<<ans<<'\n';

}
signed main()
{
    IOS;
    cin.tie(0);
    int T=1;
    while (T--)
    {
        BellaKira();
    }
}