T1 一道数论神题

题目

【题目描述】

LYK有一张无向图G={V,E}，这张无向图有n个点m条边组成。并且这是一张带权图，只有点权。

LYK想把这个图删干净，它的方法是这样的。每次选择一个点，将它删掉，但删这个点是需要代价的。

假设与这个点相连的还没被删掉的点是u₁,u₂,…,u_k。LYK将会增加 a[u₁],a[u₂],…,a[u_k]的疲劳值。

它想将所有点都删掉，并且删完后自己的疲劳值之和最小。你能帮帮它吗？

【输入格式】

第一行两个数n,m表示一张n个点m条边的图。

第二行n个数a_i表示点权。

接下来m行每行三个数u,v，表示有一条连接u,v的边。数据保证任意两个点之间最多一条边相连，并且不存在自环。

【输出格式】

你需要输出这个最小疲劳值是多少。

【输入样例】

4 3
10 20 30 40
1 4
1 2
2 3

【输出样例】

40

【数据规模】

对于30%的数据n≤10。

对于60%的数据n,m≤1000。

对于 100%的数据1≤n,m,a_i≤100000。

解析

久违的送分题

贪心思想，将每个点对与其连接的点的贡献从大到小排序，依次删除即可。

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
inline int read()
{
    int num=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9')
    {
        num=(num<<1)+(num<<3)+ch-'0';
        ch=getchar();
    }
    return num;
}
const int N=100100;
struct rec{
    int w,num;
}a[N];
int n,m,b[N];
long long ans;
bool v[N];
vector<int> edge[N];
bool cmp(rec x,rec y)
{
    return x.w>y.w;
}
int main()
{
    //freopen("god.in","r",stdin);
    //freopen("god.out","w",stdout);
    memset(v,false,sizeof(v));
    n=read(),m=read();
    for(int i=1;i<=n;i++) a[i].w=read(),a[i].num=i,b[i]=a[i].w;
    for(int i=1;i<=m;i++)
    {
        int x=read(),y=read();
        edge[x].push_back(y),edge[y].push_back(x);
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        int x=a[i].num;
        v[x]=true;
        for(int j=0;j<edge[x].size();j++)
            if(!v[edge[x][j]]) ans+=b[edge[x][j]];
    }
    cout<<ans;
    return 0;
}

 

 

 

 

 

T2 数组异或

题目

【题目描述】

xor——异或，和and与or一样，是一种重要的逻辑运算，他的运算规律是0xor 0=0，1 xor 1=0，1 xor 0=1，0 xor 1=1。

两个整数之间的异或是将两个整数转化成二进制，对他们的每一位分别进行xor操作，例：6(110) xor 13(1101) = 11(1011)

现在我们要介绍一种新的操作——数组异或，将两个相同大小（假设都为n）的数组A、B异或成一个新数组C，则新数组必满足:

现在给你数组大小n，和两个数组A,B

求他们的异或数组C

由于最终答案可能过大，你需要对C的每个元素对10⁹+7取模

【输入格式】

一共3行。

第一行一个正整数N。

接下来两行每行N个正整数，表示数组A、B。

【输出格式】

一共1行，N个正整数，表示数组C。

【输入样例】

7
20670 1316 25227 8316 21095 28379 25235
19745 6535 14486 5460 15690 1796 12403

【输出样例】

7583 52096 161325 276944 453024 675974 958287

【数据规模】

对于50%的数据，N≤100。

对于全部的数据，N≤10⁵。

解析

数论不太懂，以下是出题人的题解。

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
using namespace std;
inline int read()
{
    int num=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9')
    {
        num=(num<<1)+(num<<3)+ch-'0';
        ch=getchar();
    }
    return num;
}
const int N=133333,mod=1000000007;
int n,a[N],b[N],aa[33][2],bb[33][2];
int main()
{
    //freopen("xorarray.in","r",stdin);
    //freopen("xorarray.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++) b[i]=read();
    for(int i=1;i<=n;i++)
    {
        long long c=0;
        for(int j=0;j<=30;j++)
        {
            aa[j][(a[i]>>j)&1]++,bb[j][(b[i]>>j)&1]++;
            long long cc=((long long)aa[j][0]*bb[j][1