abc286-287题解

ABC 286 - 287

286

题意:

​ 就是交换给定字符串指定位置,swap 一下。

样例

Input:
	chokudai
	3 5
Output:
	chukodai
Code
#include <cstring>
#include <iostream>
#include <algorithm>
#include <ctime>
#include <vector>
#include <map>
using namespace std;

const int N = 100010;

int main()
{
    clock_t c1 = clock();
#ifdef LOCAL
    freopen("in.in","r", stdin);
    freopen("out.out","w",stdout);
#endif
    string s;
    cin >> s;
    int n,m;
    cin >> n >> m;
    swap(s[n-1],s[m-1]);
    cout << s;
#ifdef LOCAL
    cerr << "Time Used: " << clock() - c1 << "ms" <<endl;
#endif
    return 0;
}

题目大意:

​ 4n-1个数字(1~n) 找出那个出现了3次的数字

遍历一遍直接找到出现次数为3的输出就行了

Input:
    3
    1 3 2 3 3 2 2 1 1 1 2
Output:
	2
Code
#include <cstring>
#include <iostream>
#include <algorithm>
#include <ctime>
#include <vector>
#include <map>
using namespace std;

const int N = 1e5+10;

int main()
{
    clock_t c1 = clock();
#ifdef LOCAL
    freopen("in.in","r", stdin);
    freopen("out.out","w",stdout);
#endif
    int n;
    cin >> n;
    vector<int> cnt(n+1);

    for(int i=1,x;i<4*n;i++)
    {
        cin >> x;
        cnt[x]++;
    }
    for(int i=1;i<=n;i++)
        if(cnt[i]!=4) cout << i<<endl;
#ifdef LOCAL
    cerr << "Time Used: " << clock() - c1 << "ms" <<endl;
#endif
    return 0;
}

题目大意:

​ 给定两组字符串 \(A,B\),且\(A.size() >= B.size() 且 A[1] = B[1],A.back()=B.back()\),找出相等的字符串并输出。

​ 双指针就行了,一个指向\(A\),一个指向\(B\),如果 \(A[i] = B[j]\) 那么 \(j++\)​

样例:

Input:
	5 3
	tokyo kanda akiba okachi ueno
	tokyo akiba ueno
output:
	Yes
    No
    Yes
    No
    Yes
Code
#include <cstring>
#include <iostream>
#include <algorithm>
#include <ctime>
#include <vector>
#include <map>
using namespace std;

const int N = 1e5+10;

int main()
{
    clock_t c1 = clock();
#ifdef LOCAL
    freopen("in.in","r", stdin);
    freopen("out.out","w",stdout);
#endif
    int n,m;
    cin >> n >> m;
    vector<string> a(n),b(m);
    for(int i=0;i<n;i++) cin >> a[i];
    for(int i=0;i<m;i++) cin >> b[i]; 
    for(int i=0,j=0;i<n;i++)
    {
        if(a[i]==b[j]) j++,cout <<"Yes"<<endl;
        else cout << "No"<<endl;
    }

#ifdef LOCAL
    cerr << "Time Used: " << clock() - c1 << "ms" <<endl;
#endif
    return 0;
}

题目大意:

​ 给了\(2N\)个数字,再给出相互配对的价值,问配对N对的价值异或和最大为多少。

样例:

Input:
    2
    4 0 1
    5 3
    2
Output:
	6

解法:

​ 数据范围是 \(N<=8\) ,这时候我们就要往dfs上面想了,我们试着求下分组的方案数,

​ \(15*13*11*9*7*5*3*1 = 2027025 << 1e9\)​ 我说明我们可以暴力枚举每一种方案,但是要注意,我们枚举方案的时候要规定当前 组内是无序的,因为配对只考虑是否是相同的人。

所以我学到了新的方式来枚举

首先先从小到大找一个放进去一个没有被选的,然后我们再去枚举这个组内的其他配对元素,试着画一下我们的递归树,我们就会发现,我们组内的第一个元素是有序的,且我们组内的元素也是有序的。这样我们不会多余枚举这样的情况 \((1,2)(3,4) = (3,4)(2,1) = (4,3)(1,2)\)

​ 当然我们可以运用我们的高中知识,平均分为几组,最后方案数要除以 \(A_i^i\)​,也就是当我们 \(A_i^i * cnt == m\)​​ 我们直接强制退出程序 exit(0);

code
#include <cstring>
#include <iostream>
#include <algorithm>
#include <ctime>
#include <vector>
#include <map>
#define x first
#define y second
using namespace std;

const int N = 20;
int g[N][N];
bool st[N];
vector<pair<int,int>> path(N);
int ans,n,m;
bool flag = false;
int cnt,c=1;

void dfs(int u)
{
    if(u == n)
    {
        int t=0;
        for (int i = 0; i < n; i++)
        {
            auto zz = path[i];
            t^=g[zz.x][zz.y];
        }
        ans = max(ans,t);
        return;
    }
    int i = 1;
    while(i<=m&&st[i]) i ++;
    st[i] = true;
            for(int j=1;j<=m;j++)
            {
                if(st[j]) continue;
                st[j] = true;
                path[u] = {i,j};
                dfs(u+1);
                st[j] = false;
            }
    st[i] =false;
}

int main()
{
    clock_t c1 = clock();
#ifdef LOCAL
    freopen("in.in","r", stdin);
    freopen("out.out","w",stdout);
#endif
    cin >> n;
    m=2*n;
    for(int i=1;i<=m;i++)
        for(int j=i+1;j<=m;j++)
            cin >> g[i][j];
    dfs(0);
    cout << ans<<endl;
   
#ifdef LOCAL
    cerr << "Time Used: " << clock() - c1 << "ms" <<endl;
#endif
    return 0;
}

题目大意:

​ 给我们\(n\)​个数字,且对于每个\(i(1<=i<n)\)​ 我们\(A_i和A_{i+1}\)​​中间要至少选一个,求这样选取的中位数和平均值最大是多少?

解法:
玄学二分

前置: dp求这样选整个序列的最大值

\(f[i][j]\) : 表示 从前 \(i\)个物品选且第\(i\)个物品的状态是 \(j\) 时,选取的最大值 ( \(j\)​有两种取值,0代表不取,1代表取 )

转移方程 : \(f[i][1] = max(f[i-1][0],f[i-1][1])+b[i]\)

​ \(f[i][0]=f[i-1][1]\) 当我们这个物品不选时,上个物品必须选,如果不选则不满足至少选一个。(当然我们会发现我们只会用到上一维度可以优化)用 \(f\)代表\(f[i][1]\) 用 \(g\) 表示 \(f[i][0]\) ,如果我们更新时我们这两个值存储的是上一层的,我们更新这一维度的。

int t = max(f,g) + b[i];
g = f;
f = t;
  • 当我们求平均数时,采用的是浮点数二分,当我们枚举的数大时,我们这样选取的最大值是\(<0\) 的,当小时 \(>0\) , 当等于答案时是\(=0\),所以当 \(>=0\)​时我们要变换左边界。

  • 当我们求中位数时,是要将我们的这个数尽可能的选多点,尽可能的让他靠近中间的位置,奇数时我们中位数的位置在(n+1)/2,也就是我们不包括中位数左右两边的数一样多,偶数的时候在n/2也就是左半边最后一个数,两种情况汇总也就是说我们>=x的数严格多于小于x的数,我们将 >= x的数设为 \(1\)​ ,<x的数设为\(-1\)​,这样当我们选取的最大值>0我们这个数满足,当<0时不满足,=0时说明 x在中间偏右一个位置。

    代码

    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #include <ctime>
    #include <vector>
    #include <map>
    using namespace std;
    
    const int N = 100010;
    vector<int> a(N);
    int n;
    
    template<typename T> T check(T x,T b[])
    {
       T f = 0, g=0;
       for(int i=0;i<n;i++)
       {
           T t = max(f,g) + b[i];
           g = f;
            f = t;
       }
        return max(f,g);
    }
    
    
    
    int main()
    {
        clock_t c1 = clock();
    #ifdef LOCAL
        freopen("in.in","r", stdin);
        freopen("out.out","w",stdout);
    #endif
        cin >>n;
        for(int i=0;i<n;i++) cin >> a[i];
        double l = 1 ,r = 1e9+10;
        while(r-l>1e-5)
        {
            double b[n];
            double mid = (l + r) / 2;
            for(int i=0;i<n;i++) b[i] = a[i] - mid;
            if(check(mid,b)>=0) l=mid;
            else  r=mid;
        }
        int l1=1,r1=1e9;
        int b[n];
        while(l1<r1)
        {
            int mid = l1 + r1 + 1>>1;
            
            for(int i=0;i<n;i++) b[i] = a[i]>= mid ? 1 : -1;
    
            if(check(mid,b)>0) l1 = mid; 
            else r1 = mid - 1;
    
        }
        printf("%.2lf\n%d",l,l1);
    #ifdef LOCAL
        cerr << "Time Used: " << clock() - c1 << "ms" <<endl;
    #endif
        return 0;
    }
    

我是数学大彩笔

这个题用到了一点线代的知识( 看题解看出来的=-=)

题目大意:

​ 给\(n\)个数字的价值,问我们用某些数异或表示出来\({x,1<=x<2^n}\) 的最小价值(\(w>0,N<=16,2^N<1e6\))。

解法:贪心+数学

将价值升序排列,如果当前数能表示其他数字,能不加就不加

  • 证明1: 当当前数字能表示其他数字时,当我们不加入时,如果后面有数字可以表示这个数字多表示出来的数字,我们加入这个没有加入那个划算。我们不如直接加入那个数字,与最小价值矛盾。
  • 证明2: 当我们不能加入时,也就是当前数字不能表示新的数字,我们大可不必加入这个数字,如果加入,等于累赘,违背最小价值。
问题来了

​ 如果我们暴力去枚举当前数字与之前数字异或能表示的数字,我们会发现,我们要枚举\(2^{2n}>1e9\) 直接就超时了 ,这时候我们想空间坐标系的 单位向量,我们管它叫 基底,也就是可以使用他们三个表示我们空间坐标系的 所有向量,我们不妨代入到我们的\(XOR\)里面,当我们拥有一些 基底时::\(x_1⊕x_2⊕x_3⊕...⊕x_n\) 当我们加入\(x_i\)基底时,加入这个可以表示 新的向量,我们会发现我们\(⊕\)完以后我们在异或的 过程 中不会\(=0\),如果 出现 等于\(0\),就相当于\(x_i\)这个基底可以被其他基底表示出来,也就是不能充当基底,相反,当我们没有出现\(0\)时,我们就可以用。

这样我们的时间复杂度就变成了 \(O(N*2^N)\)​

code
#include <cstring>
#include <iostream>
#include <algorithm>
#include <ctime>
#include <vector>
#include <map>
#define x first
#define y second
using namespace std;

const int N = 16,M = 1<<N;
typedef pair<int,int> PII;
typedef long long LL;
PII a[M];
int n,m;
bool st[M];
vector<int> id;
LL ans;

int main()
{
    clock_t c1 = clock();
#ifdef LOCAL
    freopen("in.in","r", stdin);
    freopen("out.out","w",stdout);
#endif
    cin >> n; m = 1<<n;
    for(int i =1;i<m;i++) cin >> a[i].x , a[i].y = i;
    sort(a+1,a+m);
    for(int i=1;i<m;i++)
    {
        auto t = a[i];
        int s = t.y;
        for(auto idx : id) s = min( s, s^idx);
        if(s>0) id.push_back(s),ans += t.x;
    }
    cout << ans;

#ifdef LOCAL
    cerr << "Time Used: " << clock() - c1 << "ms" <<endl;
#endif
    return 0;
}

287

题目大意: 判断 输入的\(n,-2^{63}<=n<2^{63}\)​,判端 n是否为整数

#include <iostream>

using namespace std;

int main()
{
    long long n;
    int m;
    cin >> n;
    m = n;
    if( m == n) cout <<"Yes";
    else cout << "No";
    return 0;
}

题目大意: 给定 \(A\) 矩阵,输出 \(B\) 矩阵,\(A,B\)​ 矩阵行列相反

#include <cstring>
#include <iostream>
#include <algorithm>
#include <ctime>
#include <vector>
#include <map>
using namespace std;

const int N = 1;

int main()
{
    clock_t c1 = clock();
#ifdef LOCAL
    freopen("in.in","r", stdin);
    freopen("out.out","w",stdout);
#endif
    
    int n,m;
    cin >> n >> m;
    int g[n][m];
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin >> g[i][j];
    for(int j=0;j<m;j++)
    {
        for(int i=0;i<n;i++)
            cout << g[i][j] <<' ';
        cout << endl;
    }

#ifdef LOCAL
    cerr << "Time Used: " << clock() - c1 << "ms" <<endl;
#endif
    return 0;
}

题目大意: 给定一个字符串,可以在开头补无数a,问字符串经过操作后是否为回文串。

解法:分为三部分,开头 末尾a 和中间的 a

  • 如果开头的a 数量多于末尾的 ,肯定不是。

  • 中间部分是回文串则是。

    Code
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #include <ctime>
    #include <vector>
    #include <map>
    using namespace std;
    
    const int N = 1;
    
    int main()
    {
        clock_t c1 = clock();
    #ifdef LOCAL
        freopen("in.in","r", stdin);
        freopen("out.out","w",stdout);
    #endif
        
        string s;
        cin >> s;
        int i=0,j=s.size()-1;
        while(i<=j&&s[i]=='a') i ++;
        while(j>=0&&s[j]=='a') j --;
        bool f = true;
        if(i>s.size()-1-j) f = false;
        else
        {
            while(i<j)
            {
                if(s[i] != s[j])
                {
                    f = false;
                    break;
                }
                i++,j--;
            }
        }
        if(f) cout << "Yes";
        else cout << "No"; 
    
    #ifdef LOCAL
        cerr << "Time Used: " << clock() - c1 << "ms" <<endl;
    #endif
        return 0;
    }
    
    

题目大意:开始 \(A=(0)\) , 给一些操作序列,第\(i\)个如果是\(L\) , 我们就将他插到\(i-1\)的左边,\(R\)就是右边,输出最后的序列。

尝试

如果正着想我们会发现十分复杂,我们首先要找到当前字符串的 \(i-1\)的位置,将其插入。 复杂度十分高,我们模拟一遍会发现,我们倒着看的时候,我们发现,操作变成了 一堆字符串。模拟一下 吧,

3
LLR
reverse(s);
string ans = "3";
// R = 23
// L = 231 
// L = 2310

string ans = "0";
// L = 10
// L = 210
// R = 2310

我们发现如果是 R 说明当前这一坨在 后边 ,反之在前边,我们可以用双端队列(用字符串模拟会超时=-=)

Code
#include <cstring>
#include <iostream>
#include <algorithm>
#include <ctime>
#include <string>
#include <vector>
#include <map>
#include <queue>
using namespace std;

const int N = 200010;
deque<int> q;
int main()
{
    clock_t c1 = clock();
#ifdef LOCAL
    freopen("in.in","r", stdin);
    freopen("out.out","w",stdout);
#endif
    string l,r;
    int n;
    cin >> n;
    
    string a;
    cin >> a;
    
   
    q.push_back(n);
    for(int i = n-1;~i;i--)
    {
        if(a[i] == 'R')
            q.push_front(i);
        else
            q.push_back(i);
    }
    for(auto t : q)
        cout << t << ' ';



#ifdef LOCAL
    cerr << "Time Used: " << clock() - c1 << "ms" <<endl;
#endif
    return 0;
}

有兴趣的去写写

题意: 有\(n\)个空间站,给一些数据,表示空间站的高度是多少,\(x-->y\) 如\(h[x]>=h[y]\) 那么价值是\(h[x] - h[y]\),反之是\(2(h[x]-h[y])\)​,求最大价值。

SPFA已死

这个用 \(Dijkstra\)​ 挺秒的,\(dist[i]\)​ 表示我们\(1-->i\)​ 的最小价值,将负边转正,对于<0的边我们将其转正,对于大于0的边,我们将其变为0,我们每次更新\(ans\)​时采用,\(ans = max(ans,h[1]-h[i]-d[0])\),这里配合那里简直妙蛙种子,首先我们试着代值进去,我们会发现这就是我们的价值。具体是什么样子呢,就是我们的我们到了那个点,我们的价值就是 \(h[x]-h[y]-w\) 当我们\(x>=y\)是 \(w=0\),\(x<y\) 时\(w=h[y]-h[x]\)​。

Code
#include <cstring>
#include <iostream>
#include <algorithm>
#include <ctime>
#include <vector>
#include <map>
#include <queue>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N = 200010,M=2*N;
int h[N],e[M],w[M],ne[M];
int height[N];
int idx,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++;
}
int main()
{
    clock_t c1 = clock();
#ifdef LOCAL
    freopen("in.in","r", stdin);
    freopen("out.out","w",stdout);
#endif
    int n,m;
    cin >> n >> m;
    for(int i=1;i<=n;i++) cin >> height[i];
    memset(h,-1,sizeof h);
    for(int i=1,a,b;i<=m;i++)
    {
        cin >> a >> b;
        add(a,b,max(0,height[b]-height[a]));
        add(b,a,max(0,height[a]-height[b]));   
    }
    priority_queue<PII,vector<PII>,greater<PII>> q;
    memset(dist,0x3f,sizeof dist);
    q.push({0,1});
    dist[1]=0;
    int ans=0;
    for(int i=0;i<n;i++)
    {
        auto t = q.top();
        q.pop();
        int k = t.second,d = t.first;
        if(st[k]) continue;
        st[k] = true;
        // cout << k <<' ';
        ans = max(ans, height[1] - height[k] - dist[k]);
        for(int i=h[k];~i;i=ne[i])
        {
            int j=e[i];
            if(dist[j] > dist[k] + w[i])
            {
                dist[j] = dist[k] + w[i];
                q.push({dist[j],j});
            }
        }
    }
    cout << ans;

#ifdef LOCAL
    cerr << "Time Used: " << clock() - c1 << "ms" <<endl;
#endif
    return 0;
}

题目大意:给我们可选数字的范围,和要组成序列的长度,要我们求出,该长度下 满足 \(LIS\) 长度为3 序列数有多少。

解法:dp

\(f[i][j][k][l]\)​ :表示长度为 \(i\) 的序列,\(LIS\) 是\((j,k,l)\) 的方案数。

abc286-287题解

#include <cstring>
#include <iostream>
#include <algorithm>
#include <ctime>
#include <vector>
#include <map>
#define for_i(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

const int N = 1010,M=15,mod=998244353;
int f[N][M][M][M];

int main()
{
    clock_t c1 = clock();
#ifdef LOCAL
    freopen("in.in","r", stdin);
    freopen("out.out","w",stdout);
#endif
    int n,m;
    cin >> n >> m;
    f[0][m+1][m+1][m+1] = 1;
    for_i(i,1,n)
        for_i(j,1,m+1)
            for_i(k,1,m+1)
                for_i(l,1,m+1)  
                    for_i(x,1,m)
                    {
                        if(x<=j) (f[i][x][k][l] += f[i-1][j][k][l] ) %= mod;
                        else if(x<=k) (f[i][j][x][l] += f[i-1][j][k][l]) %=mod;
                        else if(x<=l) (f[i][j][k][x] += f[i-1][j][k][l]) %= mod;
                    }
                

    int ans=0;
    for_i(i,1,m)
        for_i(j,i+1,m)
            for_i(k,j+1,m)
                (ans+=f[n][i][j][k])%=mod;
    cout << ans;

#ifdef LOCAL
    cerr << "Time Used: " << clock() - c1 << "ms" <<endl;
#endif
    return 0;
}
上一篇:es6 filter() 方法总结


下一篇:C++重载前置和后置++运算符