比赛题目很简单嘛，认真做了寒假训练的同学随便三题吧，考察的所有知识点全部都在 寒假训练里面出现过 A：有一个小trick而已嘛，怎么那么多人爆零了，因为是连续的，所以两者之
比赛题目很简单嘛，认真做了寒假训练的同学随便三题吧，考察的所有知识点全部都在
寒假训练里面出现过
A：有一个小trick而已嘛，怎么那么多人爆零了，因为是连续的，所以两者之间的差值一旦超过1就输出NO，然后考虑一下0 0这种特殊情况，0 0这种情况输出NO就行了，就算是在原地，原地的那一级阶梯也要算进奇数或者偶数里面，所以0 0一定不正确
#include <bits/stdc++.h>using namespace std;
int main(){
//freopen("A.in", "r", stdin);
//freopen("A.out", "w", stdout);
int a,b;
while(~scanf("%d%d",&a,&b)){
if(a == 0&&b == 0) puts("NO");
else if(abs(a-b) > 1) puts("NO");
else puts("YES");
}
return 0;
}
B：就判断一下p是不是素数以及写一个快速幂就可以了，因为题目数据不大，所以判断素数那一块不优化也可以过，另外需要long long保存，防止溢出
#include <bits/stdc++.h>using namespace std;
bool prime(__int64 a)
{
__int64 i;
for(i=2; i*i<=a; i++)
{
if(a%i == 0)return false;
}
return true;
}
bool q_pow(__int64 a,__int64 b)
{
__int64 res=1,mod=b,carry=a;
while(b)
{
if(b%2)
{
res=res*a%mod;
}
a=a*a%mod;
b>>=1;
}
if(res == carry)return true;
else return false;
}
int main()
{
//freopen("B.in", "r", stdin);
//freopen("B.out", "w", stdout);
__int64 p,a;
while(~scanf("%I64d%I64d",&p,&a))
{
if(!prime(p) && q_pow(a,p))puts("yes");
else puts("no");
}
return 0;
}
C：但是考虑数据极限以及1s的时限，贪心不可过，考虑使用数据结构，最通用也是最容易想到的办法就是使用优先队列来保存数，重定义一下优先级，然后每次取出队头的两个元素，加起来再放进优先队列中，最后队列中的元素即是我们所需要的结果
#include <bits/stdc++.h>using namespace std;
typedef long long ll;
struct node
{
ll m;
bool operator<(const node &a) const
{
return a.m<m;
}
};
int main()
{
//freopen("C.in","r",stdin);
//freopen("C.out","w",stdout);
ll i,j,n,sum;
priority_queue<node>Q;
node p,q;
while(~scanf("%I64d",&n))
{
for(i=0; i<n; i++)
{
scanf("%I64d",&p.m);
Q.push(p);
}
sum=0;
for(i=0; i<n-1; i++)
{
p=Q.top(),Q.pop();
q=Q.top(),Q.pop();
sum += p.m+q.m;
p.m = p.m+q.m;
Q.push(p);
}
while(!Q.empty())
Q.pop();
printf("%d\n",sum);
}
return 0;
}
另外附上堆的解法：
#define MAXN 10100
using namespace std;
int n;
long long Ans = 0;
int heap[MAXN],size = 0;
void Adjust(int k,int len){
int left_node = 2*k, right_node = 2*k+1, root = k;
if (root <= len/2){
if (left_node <= len && heap[left_node] < heap[root]) root = left_node;
if (right_node <= len && heap[right_node] < heap[root]) root = right_node;
//找出当前节点最小的，如果根节点就是最小的，不必再往下找
if (root != k) {
swap(heap[k],heap[root]);
Adjust(root,len);//维护以交换的结点为根的子堆
}
}
}
void HeapWork(int len){
int Root;
for (int i=len;i>=2;i--) {
Root = heap[1];//取出跟（最小的一堆）
heap[1] = heap[i];
Adjust(1,i-1);//重新调整，找到第二小的
heap[1] += Root;//将最小的两堆合并，加入堆
Ans += heap[1];
Adjust(1,i-1);//维护小根堆
}
}
int main(){
while(cin >> n){
Ans = 0;
for (int i=1;i<=n;i++) scanf("%d",&heap[i]);
sort(heap+1,heap+n+1);
//初始化：读入后先排序预处理，建立小根堆。
HeapWork(n);//合并果子
cout << Ans <<endl;
}
return 0;
}
D：题目描述比较复杂，但是读懂了之后题意就明确了，总花费的时间ans=(n-c[j])*a[i]，b[i]+d[j]<=s，由于第二类法术是不递减的，所以可以枚举第一类法术，然后二分第二类法术，保证法力值非负，在耗法力值相同的法术情况下取产生蛋糕数量多的法术
#include <bits/stdc++.h>typedef long long ll;
using namespace std;
const int maxn = 2e5+10;
ll a[maxn],b[maxn],c[maxn],d[maxn];
int main()
{
//freopen("D2.in", "r", stdin);
//freopen("D3.out", "w", stdout);
ll n,m,k,x,s;
while(scanf("%lld%lld%lld",&n,&m,&k)!=EOF)
{
scanf("%lld%lld",&x,&s);
for(int i=0; i<m; ++i)
scanf("%lld",&a[i]);
for(int i=0; i<m; ++i)
scanf("%lld",&b[i]);
for(int i=1; i<=k; ++i)
scanf("%lld",&c[i]);
for(int i=1; i<=k; ++i)
scanf("%lld",&d[i]);
ll ans =(n - c[upper_bound(d+1,d+k+1,s)-d-1]) * x;
for(int i=0; i<m; ++i)
{
if(b[i]>s)
continue;
ans = min(ans, (n - c[upper_bound(d+1,d+k+1,s-b[i])-d-1]) * a[i]);
}
printf("%lld\n",ans);
}
return 0;
}
E：给出n只手套，最多k个颜色，一共m天，每天都要戴某两只手套，不能让某一天戴不同颜色的手套，问至少改变多少只手套的颜色。思路：把在同一天穿的手套用并查集放到一起，然后找出最多的那种颜色，size-max即为这堆手套至少要改的次数。两种解法，并查集，dfs：
并查集解法：
#include <bits/stdc++.h>using namespace std;
const int maxn = 2e5 + 5;
int pre[maxn], a[maxn], b[maxn];
vector<int> v[maxn];
int Find(int x)
{
if(pre[x] != x) pre[x] = Find(pre[x]);
return pre[x];
}
void join(int x, int y)
{
pre[Find(y)] = Find(x);
}
int main()
{
int n, m, k, x, y;
while(~scanf("%d%d%d", &n, &m, &k))
{
for(int i = 0;i <= maxn;i++)
v[i].clear();
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]), pre[i] = i;
for(int i = 1; i <= m; i++)
scanf("%d%d", &x, &y), join(x, y);
int cnt = 1;
for(int i = 1; i <= n; i++)
{
if(pre[i] == i)
b[i] = cnt++;
}
for(int i = 1; i <= n; i++)
{
v[b[Find(i)]].push_back(a[i]);
}
int ans = 0;
for(int i = 1; i < cnt; i++)
{
int maxx = 0;
map<int, int> mm;
for(int j = 0; j < v[i].size(); j++)
{
mm[v[i][j]]++;
if(mm[v[i][j]] > maxx) maxx = mm[v[i][j]];
}
ans += v[i].size() - maxx;
}
printf("%d\n", ans);
}
return 0;
}
dfs解法：
using namespace std;
typedef long long ll;
int n,m,k;
int x[200005];
vector<vector<int> >v;
int cnt[200005];
int ans,mxc,c;
int vs[200005];
void dfs1(int node)
{
vs[node]=1;
for(int i=0; i<v[node].size(); i++)
{
if(vs[v[node][i]]==0)
{
vs[v[node][i]]=1;
cnt[x[v[node][i]]]++;
if(cnt[x[v[node][i]]]>mxc)
{
mxc=cnt[x[v[node][i]]];
c=x[v[node][i]];
}
dfs1(v[node][i]);
}
}
}
void dfs2(int node)
{
vs[node]=2;
for(int i=0; i<v[node].size(); i++)
{
if(vs[v[node][i]]==1)
{
vs[v[node][i]]=2;
cnt[x[v[node][i]]]=0;
if(x[v[node][i]]!=c)
ans++;
x[v[node][i]]=c;
dfs2(v[node][i]);
}
}
}
int main()
{
while(cin>>n>>m>>k)
{
ans=0;
memset(x,0,sizeof(x));
v.clear();
for(int i=0; i<n; i++)
cin>>x[i];
v.resize(n);
for(int i=0; i<m; i++)
{
int a,b;
cin>>a>>b;
a--,b--;
v[a].push_back(b);
v[b].push_back(a);
}
fill(cnt,cnt+200005,0);
fill(vs,vs+200005,0);
for(int i=0; i<n; i++)
{
if(vs[i]==0)
{
mxc=1;
c=x[i];
cnt[x[i]]++;
dfs1(i);
cnt[x[i]]--;
if(x[i]!=c)
{
x[i]=c;
ans++;
}
dfs2(i);
}
}
cout<<ans<<endl;
}
return 0;
}