2019 年 第二届信息科学与工程学院院赛-正式赛(赛后补题)
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 是为了起点的初始化
#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）
#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 就输出那个就行了
#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
#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 才能过 数据比较大
#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 即可。
#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 用了大数据，那么我这个代码应该过不了了，思路是如果一个数的素因子个数为奇数的话，那么结果减去这个数，如果为偶数的话，那么结果就加上这个数。关于埃式筛法与欧拉筛法，后面弄懂了就再补一下！
#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 了，解题思路就是看输入的两个端点是否有相同的父节点，如果有的话，那么就会形成一个环，就会出现题目所述现象。
#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 后缀的最大值即可判断
#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)
#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;
}未完待续。。。
学如逆水行舟，不进则退Contributors
Choi Yang