练习 13

practise

A OUHE_csc

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%d", (a | b) - (a & b));
    return 0;
}

B OUHE_csc

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 2e6 + 10;
int a[N];
int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        for(int i = 1; i <= n * 2; i ++)  scanf("%d", &a[i]);
        sort(a + 1, a + n * 2 + 1);
        printf("%d\n", a[n]);
    }
    return 0;
}

C OUHE_csc

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int p[10];
LL a[N];
int main()
{
    for(int i = 1; i < 10; i ++)
    {
        p[i] = 1;
        for(int j = 0; j < 5; j ++)  p[i] *= i;
    }
    for(int i = 2; i < N; i ++)
    {
        a[i] = a[i - 1];
        int x = i, sum = 0;
        while(x)  sum += p[x % 10], x /= 10;
        if(sum == i)  a[i] += i;
    }
    int t;
    scanf("%d", &t);
    while(t --)
    {
        int n;
        scanf("%d", &n);
        printf("%lld\n", a[n]);
    }
    return 0;
}

D OUHE_csc

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 210;
int a[N];
LL f[N][N];
int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)  scanf("%d", &a[i]);
    for(int len = 3; len <= n; len ++)
        for(int i = 1; i + len - 1 <= n; i ++)
        {
            int j = i + len - 1;
            f[i][j] = 1e18;
            for(int k = i + 1; k < j; k ++)
                f[i][j] = min(f[i][j], f[i][k] + f[k][j] + (LL)a[i] * a[k] * a[j]);
        }
    printf("%lld", f[1][n]);
    return 0;
}

H 15291200127

#include <set>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
#define mem(a,b) memset(a,b,sizeof (a))
#define gcd(a,b) __gcd(a,b)
#define all(a) a.begin(),a.end()
#define in(a) insert(a)
#define sz() size()
#include<cstdlib>
#define endl '\n'
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn=100010;
const ll inf=1e18;
const ll mod=1e9+7;
const double pi=3.14159265358979;
const double ep=0.0;
vector<vector<pair<ll,ll>>>vec;
ll n,m;
void dfs(ll v,ll t,vector<ll>&d,vector<ll>&w)
{
    if (w[v]!=-1)
        return ;
    if (t==v)
    {
        w[v]=1;
        return ;
    }
    w[v]=0;
    for (auto i:vec[v])
    {
        ll u=i.first,r=i.second;
        if (d[u]+r==d[v])
        {
            dfs(u,t,d,w);
            w[v]=(w[v]+w[u])%mod;
        }
    }
}
void dij(ll s,vector<ll>&d,vector<ll>&w)
{
    d.resize(n,mod*mod);
    w.resize(n,-1);
    d[s]=0;
    set<pair<ll,ll>>se;
    se.insert({d[s],s});
    while (!se.empty())
    {
        ll v=se.begin()->second;
        se.erase(se.begin());
        for (auto i:vec[v])
        {
            ll u=i.first,r=i.second;
            if (d[u]>d[v]+r)
            {
                se.erase({d[u],u});
                d[u]=d[v]+r;
                se.insert({d[u],u});
            }
        }
    }
    for (ll i=0;i<n;i++)
        dfs(i,s,d,w);
}
int main()
{
    ll s,t;
    cin>>n>>m>>s>>t;
    s--;
    t--;
    vec.resize(n);
    for (ll i=0;i<m;i++)
    {
        ll v,u,w;
        cin>>v>>u>>w;
        v--;
        u--;
        vec[v].pb({u,w});
        vec[u].pb({v,w});
    }
    vector<ll>ds,ws,dt,wt;
    dij(s,ds,ws);
    dij(t,dt,wt);
    ll ans=ws[t]*wt[s],al=ds[t];
    for (ll i=0;i<n;i++)
    {
        if (ds[i]+dt[i]!=al)
            continue;
        if (ds[i]==dt[i])
            ans=(ans-ws[i]*wt[i]%mod*ws[i]%mod*wt[i]%mod+mod)%mod;
    }
    for (ll i=0;i<n;i++)
        for (auto j:vec[i])
        {
            ll u=j.first,w=j.second;
            if (ds[i]+dt[u]+w!=al)
                continue;
            if (w>abs(dt[u]-ds[i]))
                ans=(ans-ws[i]*wt[u]%mod*ws[i]%mod*wt[u]%mod+mod)%mod;
        }
    cout<<ans<<endl;
    return 0;
}