Skip to content

2019 年 第二届信息科学与工程学院院赛-正式赛(赛后补题)

作者:Choi Yang
发表于:2019-06-20
更新于:6 个月前
字数统计:2.2k 字
阅读时长:10 分钟
阅读量:

TIP

文章编写于 2019 年 06 月 20 日 —— 发表完失败感想之后,想着还是要继续比赛,先补完题再说,跌倒了再爬起来。

1500:XP 的矩阵

分析:

这道题注意只能向下或者向右移动,令 dp(i,j)表示 XP 学长走到位置为(x,y)时路径和的最小值,因此你可以得到状态转移方程 dp(i,j) = min(dp(i-1,j),dp(i,j-1)) +a(i,j)。

注意初始化的时候让其他地方变为最大值,保证在矩阵内行走,然后 dp[1][0]=dp[0][1]=0 是为了起点的初始化

c
#include<bits/stdc++.h>
#define mst(a) memset(a,0x3f,sizeof(a))
using namespace std;
const int maxn=1000+8;
map<int,int> mp;
map<int,int>::iterator it;
int g[maxn][maxn];
int dp[maxn][maxn];
int n;

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        mst(dp);
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                cin>>g[i][j];
            }
        }
        dp[1][0]=dp[0][1]=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                dp[i][j]=min(dp[i-1][j],dp[i][j-1])+g[i][j];
            }
        }
        int res=dp[n][m];
        cout<<res<<endl;
    }
    return 0;
}

1504: XP 的二进制操作数列

分析:

这道题挺有意思的,看懂了就是一个水题,为了使得数列中所有数字变为零,你需要使得它们先成为相同的某个数字,考虑 or 操作,那么你只需要 or 上一个二进制下位数全为 1 的数 y,即可让一个数 x 变成 y,之后你只需要再 xor 一次 y 即可得到全零的数列,另外题目的坑点在于可能初始时数列就是完全相同的。并且如果数列全为 0 的话要特别考虑 全 0 不需要操作,所以操作次数为 0

那么就很显然了,如果数列完全相同(除开全 0)操作次数为 1 (与自己异或就行了),不完全相同就 2 次 (先 or 一个 2 的 32 次方-1 的数 使自己变为全 1 然后再异或这个全 1 操作次数为 2)

c
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+8;
long long a[maxn];
set<long long >st;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        st.clear();
        int n;
        cin>>n;
        bool flag=false;
        for(int i=0;i<n;i++)
        {
            long long x;
            cin>>x;
            if(x!=0)
            {
                flag=true;
            }
            st.insert(x);
        }
        if(flag)
        {
             int len=st.size();
            if(len!=1)
            {
                cout<<2<<endl;
            }
            else
            {
                cout<<1<<endl;
            }
        }
        else
        {
            cout<<0<<endl;
        }
    }
    return 0;
}

1505: XP 的橘子洲

分析:

这个题原本学长是想考我们 xor 异或操作的,但是我用 map 做了,因为那个特别的烟花只有 1 个 所以对所有烟花,相同的就++ 然后如果 value 值为 1 就输出那个就行了

c
#include<bits/stdc++.h>
#define mst(a) memset(a,0,sizeof(a))
using namespace std;
const int maxn=1000000+8;
int a[maxn];
map<int,int> mp;
map<int,int>::iterator it;
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        mp[x]++;
    }
    for(it=mp.begin();it!=mp.end();it++)
    {
        if(it->second==1)
        {
            cout<<it->first<<endl;
        }
    }
    return 0;
}

INFO

经过暑假刷题后,明白了异或操作,特来补上简单异或操作!

位异或: 一个数与 0 异或 等于它本身 一个数与自己异或 等于 0

即对于一个任意一个数 n,它有几个特殊的性质:

1、0^n = n

2、n^n = 0 所以可以通过每次异或运算,最后剩下的值就是出现奇数次的那个数字。

==另外,附上位异或的一些运算法则==

1、a^b = b^a

2、(a ^ b) ^ c = a ^ ( b ^ c )

3、a ^ b ^a = b

c
#include<iostream>
using namespace std;
const int maxn=1e6+8;
int a[maxn];
int main()
{
    int n;
    cin>>n;
    int res=0;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        res^=x;
    }
    cout<<res<<endl;
    return 0;
}

1507: XP 的买卖

分析

树状数组的模板题,但是我们需要注意的是树状数组没有单点替换的操作 只有更新这种做法,所以我们就先把原来的那个值减去,然后再加上我们新输入的值。其他的就是模板了,然后注意这个题 long long 才能过 数据比较大

c
#include<bits/stdc++.h>
#define mst(a) memset(a,0,sizeof(a))
using namespace std;
const int maxn=100000+8;
map<int,int> mp;
map<int,int>::iterator it;
int a[maxn];
long long c[maxn];
int n,m;
void change(int pos,int v)
{
    for(int i=pos;i<=n;i+=i&(-i))
        c[i]+=v;
}
long long sum(int x)
{
    long long ans=0;
    while(x>0)
    {
        ans+=c[x];
        x-=x&(-x);
    }
    return ans;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        mst(c);
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            change(i,a[i]);
        }
        while(m--)
        {
            int op,x,y;
            cin>>op>>x>>y;
            if(op==1)
            {
                //cout<<sum(y)<<"  "<<sum(x-1)<<endl;
                cout<<sum(y)-sum(x-1)<<endl;
            }
            else
            {
                change(x,y-a[x]);
                a[x]=y;
            }
        }
    }
    return 0;
}

1508: XP 的梅溪湖

分析:

Dirac 定理:设一个无向图中有 N 个顶点,若所有顶点的度数大于等于 N/2,则哈密顿回路一定存在。 根据题意你只需要输出 YES 即可。

c
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int x,y;
        cin>>x>>y;
    }
    cout<<"Yes"<<endl;
    return 0;
}

1513: XP 的数论

分析:

这个题用埃式筛素数法或者用欧拉筛法来求,不会被卡时间,然而我这的解法并没有筛,要是 OJ 用了大数据,那么我这个代码应该过不了了,思路是如果一个数的素因子个数为奇数的话,那么结果减去这个数,如果为偶数的话,那么结果就加上这个数。关于埃式筛法与欧拉筛法,后面弄懂了就再补一下!

c
#include<bits/stdc++.h>
using namespace std;
set<int> st;
int f(int n)
{
    st.clear();
    if(n==2)
    {
        st.insert(2);
    }
    else if(n<2)
    {
        st.clear();
    }
    else
    {
        for(int i=2;i<=sqrt(n);i++)
        {
            if(n%i==0)
            {
                n/=i;
                st.insert(i);
                i--;
            }
        }
        st.insert(n);
    }
    int k=st.size();
    return k;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        long long sum=0;
        for(int i=1;i<=n;i++)
        {
            int k=f(i);
            if(k%2==0)
            {
                sum+=i;
            }
            else
            {
                sum-=i;
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}

1515: XP 的校园漫步

分析:

并查集的模板题,开始我的并查集写错了,请教别人好久才把这个题给 AC 了,解题思路就是看输入的两个端点是否有相同的父节点,如果有的话,那么就会形成一个环,就会出现题目所述现象。

c
#include<bits/stdc++.h>
#define mst(a) memset(a,0,sizeof(a))
using namespace std;
const int maxn=1000000+8;
int pre[maxn];
int find_pre(int x)
{
    if(x!=pre[x])
    {
        pre[x]=find_pre(pre[x]);
    }
    return pre[x];
}
void join(int x,int y)
{
    int a=find_pre(x);
    int b=find_pre(y);
    if(a!=b)
    {
        pre[a]=b;
    }
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            pre[i]=i;
        }
        bool flag=false;
        for(int i=0;i<m;i++)
        {
            int x,y;
            cin>>x>>y;
            if(find_pre(x)==find_pre(y))
            {
                flag=true;
            }
            else
            {
                join(x,y);
            }
        }
        if(flag)
        {
            cout<<"YES"<<endl;
        }
        else
        {
            cout<<"NO"<<endl;
        }
    }
    return 0;
}

1516: XP 的岳麓山

分析:

一道模拟题,我感觉我的方法还是比较复杂!题解:你需要分别遍历 a,b 两次,每次记录 a 前缀的最大值,b 后缀的最大值即可判断

c
#include<bits/stdc++.h>
#define mst(a) memset(a,0,sizeof(a))
using namespace std;
const int maxn=1000000+8;
map<int,int> mp;
map<int,int>::iterator it;
int a[maxn];
int b[maxn];
int res[maxn];
int main()
{
    int n;
    cin>>n;
    mst(a);
    mst(b);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {
        cin>>b[i];
    }
    int ans1=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]>=ans1)
        {
            ans1=a[i];
            mp[i]++;
        }
    }
    int ans2=0;
    for(int i=n;i>=1;i--)
    {
        if(b[i]>=ans2)
        {
            ans2=b[i];
            mp[i]++;
        }
    }
    int k=0;
    for(it=mp.begin();it!=mp.end();it++)
    {
        if(it->second==2)
        {
            res[k++]=it->first;
        }
    }
    if(k)
    {
        for(int i=0;i<k;i++)
        {
            if(i!=k-1)
            {
                cout<<res[i]<<" ";
            }
            else
            {
                cout<<res[i]<<endl;
            }
        }
    }
    else
    {
        cout<<"none"<<endl;
    }


    return 0;
}

1517: XP 的连续字符串

分析:

遍历字符串,每次判断当前字符与前一个字符是否相同,如果相同即更新当前连续的长度,并判断是否需要更新答案,另外如果当前连续长度和当前记录的最长的长度相同,即判断字典序的大小即可。O(N)

c
#include<bits/stdc++.h>
#define mst(a) memset(a,0,sizeof(a))
using namespace std;
const int maxn=1000000+8;
map<int,int> mp;
map<int,int>::iterator it;
int a[maxn];
int b[maxn];
int res[maxn];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        string str;
        cin>>str;
        int curdd=0;
        int dd=0;
        int curcnt=1;
        int cnt=1;
        for(int i=1;i<n;i++)
        {
            if(str[i]==str[curdd])
            {
                curcnt++;
            }
            else
            {
                if(curcnt>cnt)
                {
                    cnt=curcnt;
                    dd=curdd;
                }
                if(curcnt==cnt)
                {
                    if(str[dd]>str[curdd])
                    {
                        dd=curdd;
                    }
                }
                curcnt=1;
                curdd=i;
            }

        }
        cout<<str[dd]<<endl;

    }

    return 0;
}

未完待续。。。

c
学如逆水行舟,不进则退

Contributors

Choi Yang