AcWing第85场周赛

这场周赛是手速局hh

死或生

某国正在以投票的方式决定 2 名死刑犯（编号 1～2）的生死。

共有 n 组人员（编号 1～n）参与投票，每组 10 人。

每组成员只参与一名死刑犯的投票，其中第 i 组人员的投票对象是死刑犯 ti，其中 xi 人认为他无罪，yi 人认为他有罪。

在所有人员投票结束后，将对投票结果进行统计。

对于每名死刑犯，如果投他无罪的总票数大于或等于投他有罪的总票数，则他得以生还，否则他将被处死。

请你判断每名死刑犯的生死。

输入格式
第一行包含一个整数 n。

接下来 n 行，每行包含三个整数 ti,xi,yi。

保证两名犯人都会被投票。

输出格式
如果第一位死刑犯生还，则在第一行输出 LIVE，否则在第一行输出 DEAD。

如果第二位死刑犯生还，则在第二行输出 LIVE，否则在第二行输出 DEAD。

数据范围
\(前 3 个测试点满足 2≤n≤10。\)
\(所有测试点满足 2≤n≤1000，1≤ti≤2，0≤xi,yi≤10，xi+yi=10。\)

输入样例1：

2
1 5 5
2 6 4

输出样例1：

LIVE
LIVE

输入样例2：

3
1 0 10
2 0 10
1 10 0

输出样例2：

LIVE
DEAD

简单的枚举即可，借助哈希表记录无罪票数和有罪票数

#include 
using namespace std;
int a[3],b[3];
int n;
int main()
{
    cin>>n;
    while (n--)
    {
        int t,x,y;
        cin>>t>>x>>y;
        a[t]+=x;
        b[t]+=y;
    }
    
    for (int i=1;i<=2;i++)
        if (a[i]>=b[i])
            puts("LIVE");
        else puts("DEAD");
    
    return 0;
}

最大价值

已知，小写字母 a～z 的价值分别为$ w_a,w_b,…,w_z$。

对于一个由小写字母构成的长度为 l 的字符串 \(S=s_1,s_2…s_l，其价值为 w_{s1}×1+w_{s2}×2+…+w_{sl}×l\)。

现在，给定一个由小写字母构成的字符串 S，请你在这个字符串中插入 k 个小写字母，要求最终得到的字符串的价值尽可能大。

注意：

• 插入的位置可以随意选。
• 插入的字母也可以随意选，可以插入不同字母。

输出最大可能价值。

输入格式
第一行包含一个字符串 S。

第二行包含一个整数 k。

第三行包含 26 个整数 \(w_a,w_b,…,w_z\)。

输出格式
一个整数，表示最大可能价值。

数据范围
前 3 个测试点满足，S 的长度范围 [1,5]。
所有测试点满足，S 的长度范围 [1,1000]，\(0≤k≤10^3\)，\(w_a～w_z\) 的取值范围 [0,1000]。

输入样例：

abc
3
1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

输出样例：

41

贪心即可，经过证明（很好证）要得到最大价值，插入方法即在尾部插入k个单个价值的最大的字母

#include 
using namespace std;
const int N = 1010;
string s;
int w[N];
int k;
typedef long long LL;
int main()
{
    cin>>s>>k;
    int res=0;
    for (int i=0;i<26;i++)
        cin>>w[i],res=max(res,w[i]);
    
    LL ans=0;
    
    for (int i=0;i

1 0

1

2 1
1 2

2

3 2
1 2
2 3

4

#include 
using namespace std;
const int  N = 55;
int p[N];
int n,m;
typedef long long LL;
int find(int x)
{
    if (p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
int main()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++) p[i]=i;
    
    int cnt=n; // cnt为独立集合的数量，即连通块的数量
    while (m--)
    {
        int a,b;
        cin>>a>>b;
        int pa = find(a);
        int pb = find(b);
        if (pa!=pb)
        {
            cnt--;
            p[pa]=pb;
        }
    }
    
    printf("%lld\n",1ll<

#include 
using namespace std;
const int N = 55;
bool st[N],reaction[N][N];
int n,m;
typedef long long LL;
LL ans=1;
void dfs(int x)
{
    for (int i=1;i<=n;i++)
    {
        if (reaction[x][i]&&!st[i]) // 当前物品与1~i（除本身）有反应，即更新ans并顺着这个物品遍历
        {
            ans<<=1;
            st[i]=true;
            dfs(i);
        }
    }
}
int main()
{
    cin>>n>>m;
    while (m--)
    {
        int a,b;
        cin>>a>>b;
        reaction[a][b]=reaction[b][a]=true;
    }
    
    for (int i=1;i<=n;i++)
    {
        if (!st[i])  // 只要当前的物品还没有用过
        {
            st[i]=true;
            dfs(i);
        }
    }
    
    cout<

#include 
using namespace std;
const int N = 55 ,M = N*N; // 无向图注意边数
int e[M],h[N],ne[M],idx;
int n,m;
typedef long long LL;
bool st[N]; 
void add(int a,int b) // 经典邻接表建图add
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void dfs(int x) // dfs遍历无向图
{
    st[x]=true;
    for (int i=h[x];~i;i=ne[i])
    {
        int j = e[i];
        if (!st[j]) dfs(j);
    }
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h); // 不初始化的后果就是TLE
    while (m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b),add(b,a); // 无向图即为特殊的有向图
    }
    int cnt=0;  // 求解连通块的数量
    for (int i=1;i<=n;i++)
    {
        if (!st[i])
        {
            dfs(i);
            cnt++;
        }
    }
    
    cout<<(1ll<

#include 
using namespace std;
const int N = 55 ,M = N*N; // 无向图注意边数
int e[M],h[N],ne[M],idx;
int n,m;
typedef long long LL;
bool st[N]; 
queueq;
void add(int a,int b) // 经典邻接表建图add
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void bfs(int x) // bfs遍历无向图
{
    st[x]=true;
    q.push(x); // 借助stl
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        for (int i=h[t];~i;i=ne[i])
        {
            int j = e[i];
            if (!st[j])
            {
                st[j]=true;
                q.push(j);
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h); // 不初始化的后果就是TLE
    while (m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b),add(b,a); // 无向图即为特殊的有向图
    }
    int cnt=0;  // 求解连通块的数量
    for (int i=1;i<=n;i++)
    {
        if (!st[i])
        {
            bfs(i);
            cnt++;
        }
    }
    
    cout<<(1ll<