阿宁的柠檬

//直接输出即可
#include<iostream>
#include<cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include<queue>
#include <cmath>

using namespace std;
//#define int long long
const int N  = 1010,M = N * N * 2,INF = 0x3f3f3f3f;
typedef long long LL;
#define endl '\n'
typedef pair<int,int>PII;
//#define x first
//#define y second

void solve()
{
    int a,b,n;cin >> a >> b >> n;
    cout << n << ' ' << (LL)n * (a + b) << endl;
}

signed main()
{
    //  ios::sync_with_stdio(0), cin.tie(0);
//  int t;cin >> t;
//  while(t --)
//  {
//      solve(cnt);
//  }
    solve();
    return 0;
}

阿宁与猫咪

//n大于2的时候,全部为1,代价为2是最优的情况.n=1的时候输出1
#include<iostream>
#include<cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include<queue>
#include <cmath>

using namespace std;
//#define int long long
const int N  = 1010,M = N * N * 2,INF = 0x3f3f3f3f;
typedef long long LL;
#define endl '\n'
typedef pair<int,int>PII;
//#define x first
//#define y second

void solve()
{
    int m;cin >> m;
    if(m == 1)cout << 1 << endl << 1 << endl;
    else 
    {
        cout << 2 << endl;
        for(int i = 0; i < m; i ++)
            cout << 1 << " ";
    }
}

signed main()
{
    //  ios::sync_with_stdio(0), cin.tie(0);
//  int t;cin >> t;
//  while(t --)
//  {
//      solve(cnt);
//  }
    solve();
    return 0;
}

阿宁吃粽子

贪心:
要想使得题目所求最大,我们可以将所有数排序,同时将2^k进行排序,让二者进行一一对应就能得到最大代价
考虑如何输出方案:我们可以选用10个队列来存储对应数位上能放的数,从小到大输出得到唯一方案

#include<iostream>
#include<cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include<queue>
#include <cmath>

using namespace std;
//#define int long long
const int N  = 2e5 + 10,M = N * 2,INF = 0x3f3f3f3f;
typedef long long LL;
#define endl '\n'
typedef pair<int,int>PII;
//#define x first
//#define y second
int a[N],cnt[12];
queue<int>q[12];

void solve()
{
    int n;cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        cnt[i % 10] ++;
        cin  >> a[i];
    }

    sort(a + 1, a + n + 1);
    //将匹配的从小到大放到相应的队列里
    int p = 0;
    for(int i = 1; i <= n; i ++)
    {
        if(cnt[p] == 0)p ++;
        cnt[p] --;
        q[p].push(a[i]);
    }

    int st = 1;
    while(1)
    {
        bool ok = false;
        for(int i = st; i <= 9; i ++)
        {
            if(!q[i].empty())
            {
                cout << q[i].front() << " ";
                q[i].pop();
                ok = true;
            }
        }
        if(st == 1)st = 0;
        if(!ok)break;
    }
    cout << endl;
}

signed main()
{
    //  ios::sync_with_stdio(0), cin.tie(0);
    //  int t;cin >> t;
    //  while(t --)
    //  {
    //      solve(cnt);
    //  }
    solve();
    return 0;
}

阿宁的质数

最坏情况下我们的数组中全是质数,此时最早未出现的质数为第2e5+1个,n/ln(n),估计n取3e6合适,也能取大
我们先筛出所有的质数,又因为我们的询问范围很小,所以可以预处理出答案

#include<iostream>
#include<cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include<queue>
#include <cmath>
#include<map>

using namespace std;
//#define int long long
const int N  = 3e6 + 10,M = N * 2,INF = 0x3f3f3f3f;
typedef long long LL;
#define endl '\n'
typedef pair<int,int>PII;
//#define x first
//#define y second
int primes[N],cnt;
bool st[N];
int res[N];

void solve()
{
    int n,q;cin >> n >> q;
    for(int i = 2; i < N; i ++)
    {
        if(!st[i])primes[cnt ++ ] = i;
        for(int j = 0; i * primes[j] < N; j ++)
        {
            st[i * primes[j]] = true;
            if(i % primes[j] == 0)break;
        }
    }

    map<int,int>mp;
    int p = 0;//用来维护当前区间内的未出现过的最小质数
    for(int i = 1; i <= n; i ++)
    {
        int a;cin >> a;
        if(a < N)mp[a] = 1;
        while(mp[primes[p]])p ++;
        res[i] = primes[p];
    }
    while(q --)
    {
        int x;cin >> x;
        cout << res[x] << endl;
    }
}

signed main()
{
    //  ios::sync_with_stdio(0), cin.tie(0);
    //  int t;cin >> t;
    //  while(t --)
    //  {
    //      solve(cnt);
    //  }
    solve();
    return 0;
}

阿宁睡大觉

只有连续的两个Z会产生贡献,所以我们尽可能多的删除某一段z来增加连续的Z
处理出所有的连续z的长度,用贪心的策略从小到大排序累加直到k,每选一个就会成功增加一个相邻的ZZ
当然两端连续的z对答案是没有贡献的要特判掉,最后求出所有相邻的ZZ的个数乘4即可

#include<iostream>
#include<cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include<queue>
#include <cmath>
#include<map>

using namespace std;
//#define int long long
const int N  = 2e5 + 10,M = N * 2,INF = 0x3f3f3f3f;
typedef long long LL;
#define endl '\n'
typedef pair<int,int>PII;
//#define x first
//#define y second
vector<int>len;

void solve()
{
    int n,k;cin >> n >> k;
    int cnt = 0;
    char s[N];
    scanf("%s",s + 1);
    for(int i = 1, j; i <= n; i ++)
    {
        //处理出相同的字串
        j = i;
        while(s[j] == s[i] && j <= n)j ++;
        j --;//第一个不同位置
        if(s[i] == 'Z')cnt += j - i;
        else 
        {
            if(i != 1 && j != n)
                len.push_back(j - i + 1);
        }
        i = j;
    }

    sort(len.begin(),len.end());

    int sum = 0;
    for(auto x : len)
    {
        if(sum + x <= k)
        sum += x,cnt ++;
    }

    cout << cnt * 4 << endl;
}

signed main()
{
    //ios::sync_with_stdio(0), cin.tie(0);
    //  int t;cin >> t;
    //  while(t --)
    //  {
    //      solve(cnt);
    //  }
    solve();
    return 0;
}

阿宁去游玩

我们的魔法是翻转除自己外的其余城市的属性这里可以画图理解一下
我们改变一次后并不会使其余城市之间的属性发生逆转,相同的仍相同,不同的仍不同
所有我们在建图的时候就处理出最短的边权即可

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>

using namespace std;
//#pragma GCC optimize(3)
const int N = 2e5 + 10,M = N * 2;
typedef long long LL;
#define int long long
#define endl "\n"
typedef pair<int,int>PII;
//#define x first
//#define y second
int h[N],e[M],w[M],ne[M],idx;
int ty[N],dist[N];
bool st[N];

void add(int a,int b,int c)
{
    e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx ++;
}

void dijkstra()
{
    memset(st,0,sizeof st);
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;
    priority_queue<PII,vector<PII>,greater<PII>>q;
    q.push({0,1});
    while(!q.empty())
    {
        auto t = q.top();q.pop();
        int ver = t.second;
        if(st[ver])continue;
        st[ver] = true;
        for(int i = h[ver]; ~i; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                q.push({dist[j],j});
            }
        }
    }
}

void solve()
{
    memset(h,-1,sizeof h);
    int n,m;cin >> n >> m;
    int x,y,z;cin >> x >> y >> z;
    for(int i = 1; i <= n; i ++) cin >> ty[i];

    for(int i = 0; i < m; i ++)
    {
        int a,b;cin >> a >> b;
        if(ty[a] == ty[b])add(a,b,min(x,y + z)),add(b,a,min(x,y + z));
        else add(a,b,min(y,x + z)),add(b,a,min(y,x + z));
    }

    dijkstra();

    cout << dist[n] << endl;
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
//  int t;cin >> t;
//  while(t --)
//  {
//      solve();
//  }
    solve();
    return 0;
}