题目
A Mex Query
题目描述
Give n non‑negative integers, please find the least non‑negative integer that doesn’t occur in the n numbers.
输入
The first line is an integer T, representing the number of test cases.
For each test case:
The first line of each test case is an integer n.
The second line of each test case are n non‑negative integers ai.
(T ≤ 10, n ≤ 2 × 105, 0 ≤ ai < 231)输出
for each test case, output a line with the answer
样例输入
2 4 4 0 1 3 2 1 1样例输出
2 0
题目大意：
T组测试数据，每组给n个整数，问你n个整数里没出现的最小非负整数
这题有一点点坑吧 虽然n不大 但是输入的数字挺大的 没法用数组打标记
但是我们一想就能知道 最小的非负整数一定在0-n之内 所以 输入的数据 小于n的我们标记上
其他的大于n的 不管 然后我们从0开始 遍历标记数组 没打标记的 就输出 就ok了
B icebound的商店
题目描述
icebound在得到神殿的宝藏之后，开了一家神秘的商店。你来到了商店，发现慷慨的icebound搞了T次促销活动。在每 次促销活动中，icebound都会想出一个他喜欢的数字，如果你买的商品的总价刚好等于icebound喜欢的数字，那么你就 可以免费得到这些商品。
icebound的商店里一共有15件商品，商品的价格和这家商店一样神秘，第一件商品的价格是1元，第二件商品的价格 是2元，设第n件商品的价格为wn元，则：wn = wn−1+ wn−2(3 ≤ n ≤ 15)。
如果在某次活动中icebound喜欢的数字是 4，那么共有 4 种购买方案：
1. 买4个 第一种商品
2. 买4个 第一种商品 和1个 第二种商品
3. 买2个 第二种商品
4. 买1个 第一种商品 和1个 第三种商品
请你算出共有多少种方案可以免费购物，方案数对1000000009(109+9)取模。输入
第一行给出一个整数T，表示icebound搞了T次活动。
接下来的T行每行给出一个正整数 x，表示在这次活动中icebound喜欢的数字。
(1 ≤ T ≤ 3000, 1 ≤ x ≤ 3000)输出
输出T行，每行输出一个正整数。
第i行的正整数表示在第i 次活动中免费购物的方案数，方案数对1000000009(109+9)取模。样例输入
3 5 20 30样例输出
6 134 509
C Nim Game
题目描述
Nim is a mathematical game of strategy in which two players take turns removing objects from distinct heaps. On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap |Fṝõṃ Wìǩìqèḋìa«țȟè ḟṝèè èñćẏćḽõqèḋìa¦. The goal of the game is to avoid being the player who doesn’t have any object to remove. The player who remove the last project is the winner.
Now KK and TT are playing Nim game with the optimal strategy. There are n heaps of stones. The number of stones in i‑th heap is ai. They play this game m times, and KK is the player making the first move. During the i‑th time they play the game on the heaps whose index in interval [li , ri]. KK wants to know whether he has a winning strategy or not.输入
The input consists of several test cases. The first line of the input gives the number of test cases,T(1 ≤ T ≤ 103).
For test case, the first line contains two integers n(1 ≤ n ≤ 106 ) and m(1 ≤ m ≤ 106), representing the number of heap of stones and the game times.
The second line contains n positive integers a1, a2, ⋯ , an (1 ≤ ai ≤ 109), representing The number of stones in i‑th heap.
In the next m lines, each line contains two integers li, ri , which means the $i: KaTeX parse error: $ within math mode$th game is played on the interval[li , ri].
It’s guaranteed that ∑ n ≤ 2 × 106 and ∑ m ≤ 2 × 106．输出
For each test case, let fi represents the answer of the i-th game.
If KK has a winning strategy in the i-th game then fi=1, otherwise fi=0. Please output ∑ fi ∗ 2m-i mod 10 + 7，in which 1 ≤ i ≤ m．样例输入
3 2 1 1 1 1 2 2 1 1 2 1 2 3 2 1 2 2 1 2 2 3样例输出
0 1 2
这个题 唉
首先 题目要读懂
然后呢 m次nim博弈 会超时的 处理异或前缀和
然鹅 没想到 快速幂也会超时 预处理2的（1-2000000）次方
终于不tle了。。。。要疯了
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+7;
ll a[maxn*2+1];
ll f[maxn*2+1];
ll summ[maxn];
ll T,n,t,l,r;
ll mod=1e9+7;
int main(){
scanf("%lld",&T);
f[0]=1;
for(int i=1;i<=2000000;i++)
f[i] = f[i-1]*2%mod;
while(T--){
scanf("%lld%lld",&n,&t);
for(ll i=1;i<=n;i++){
scanf("%lld",&a[i]);
if(i==1)summ[i]=a[i];
else summ[i]=a[i]^summ[i-1];
}
ll sum=0;
for(ll i=1;i<=t;i++){
scanf("%lld%lld",&l,&r);
ll xx=summ[r]^summ[l-1];
if(xx!=0){
sum+=f[t-i];sum%=mod;
}
}
printf("%lld\n",sum%mod);
}
return 0;
}
D
E
F 神殿
题目描述
icebound通过勤工俭学，攒了一小笔钱，于是他决定出国旅游。这天，icebound走进了一个神秘的神殿。神殿由八位守护者守卫，总共由64个门组成，每一道门后都有一个迷宫，迷宫的大小均为100 × 100。icebound在迷宫中总共耗时T小时，消耗食物K公斤。历经千辛万苦之后，icebound终于穿越了迷宫，到达了神殿的中心。神殿的中心有一个宝箱。宝箱上显示有两个正整数l和r。icebound苦思冥想，终于发现一些打开宝箱的线索。你需要找到一个数P，它具有一个美妙的性质：它是[l, r]中所有数的二进制表示里，1的个数最多的一个数。如果你发现了这个美妙的数字，你就可以打开宝箱，获得巨额财富。
比如[4, 8]中：
4: 0100
5: 0101
6: 0110
7: 0111
8: 1000
二进制表示中1的个数最多的数是7，它含有3个1。输入
输入一行，两个正整数：l和r，用空格隔开，代表神殿中宝箱上显示的数。
1 ≤ T < 231,1 ≤ K ≤ 105,1 ≤ l ≤ r ≤ 2 × 109输出
一个十进制数P，代表满足条件的解。如果有多个P满足条件，输出最小的P。
样例输入
4 8样例输出
7
记录下二进制 从低位往高位补0 补到超过r了为止
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<math.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+7;
ll l,r;
int cnt;
int q[100],w;
void c(ll n){
while(n){
if(n%2==1)q[w++]=1;
else q[w++]=0;
n/=2;
}
}
int main(){
scanf("%lld%lld",&l,&r);
ll ans=0,flag=l;
c(flag);
for(int i=0;i<w;i++){
if(q[i]==0){
cnt=i;break;
}
}
ans=flag;
while(flag<=r){
q[cnt]=1;
ans=flag;
flag+=(ll)pow(2,cnt);
while(q[cnt]==1)cnt++;
}
printf("%lld\n",ans);
}
G
H 跑图
题目描述
跑图是RPG游戏中很烦躁的事情。玩家需要跑到距离他最近的传送点的位置。现在给你一张N × M的方格图，每个方格中数值0表示为平地，数值1表示为传送点，你的任务是输出一张 N × M 的矩阵， Matrixxy表示从 (x, y) 到距离它最近的传送点的距离。 这里的距离是曼哈顿距离，(x1, y1)→ (x2, y2) 的距离为∣x1 − x2∣ + ∣y1 − y2 ∣。
输入
第一行，有两个数n,m 。接下来n行，每行m个数。
数据保证至少有一个传送点。
1 ≤ n ≤ 500 , 1 ≤ m ≤ 500输出
n行，每行m个数，表示某个点到离它最近的传送点的距离。样例输入
2 3 0 0 0 1 0 1样例输出
1 2 1 0 1 0
BFS 注意边界 并不是标记过了的就不再走了 而是标记过的 要判断能不能更小 可以的话就更新
#include<bits/stdc++.h>
using namespace std;
const int maxn=500+7;
const int INF=0x3f3f3f3f;
int v[maxn][maxn];
int ans[maxn][maxn];
struct node{
int x,y;
}q[maxn*maxn];
int d[2][4]={-1,0,1,0,0,-1,0,1};
int w,n,m,x,t;
int main(){
scanf("%d%d",&n,&m);
memset(ans,INF,sizeof(ans));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&x);
if(x==1){
q[w].x=i;q[w++].y=j;
v[i][j]=1;ans[i][j]=0;
}
}
}
while(w!=t){
int xx=q[t].x;
int yy=q[t].y;
for(int i=0;i<4;i++){
int xxx=xx+d[0][i];
int yyy=yy+d[1][i];
if(xxx>0&&xxx<=n&&yyy>0&&yyy<=m){
int ne=ans[xx][yy]+1;
if(v[xxx][yyy]==0){
ans[xxx][yyy]=ne;v[xxx][yyy]=1;
q[w].x=xxx;q[w++].y=yyy;
}
else if(v[xxx][yyy]==1&&ans[xxx][yyy]>ne){
ans[xxx][yyy]=ne;q[w].x=xxx;q[w++].y=yyy;
}
}
}
t++;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
printf("%d ",ans[i][j]);
}printf("\n");
}
return 0;
}
I
J
K
水题 快速幂
L
签到题 A+B
京公网安备 11010502036488号