2019中国大学生程序设计竞赛（CCPC） - 网络选拔赛
1001 ^&^
题目链接
题意：找到最小的c，满足(a^c)&(b^c)最小，a、b给定
思路：将a、b转化二进制，若a、b的某一位都为1，则c的一位一定为1。此外，c的每一位都是任意的。所以C的最小就是a&b。当a&b==1的时候特判为0。
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int t;
ll a,b;
void input(){
scanf("%lld%lld",&a,&b);
if((a&b)==0)
printf("1\n");
else
printf("%lld\n",a&b);
}
int main(){
scanf("%d",&t);
while(t--){
input();
// solve();
}
} 1002 array
题目链接
题意：给你n个数字，范围在[1,n]之间，且保证数字唯一（即给你n个数字的某种排列）。给你两种操作。1、将下标为pos的数字增加1e7。2、查询[1,r]之间，不与a[i]相等并且大于等于k的数值。
思路：当某一位数值增加了1e7，代表原数值空出来可以作为答案，可放在set中查询。对于查询，建后缀主席树查询包含其中，且大于k的值。答案和set中的最小大于k值取min。
#include <bits/stdc++.h>
#define maxn 100005
typedef long long ll;
using namespace std;
int n,m;
int a[maxn];
struct node{
int l,r,cnt;
node(){
l=r=cnt=0;
}
}T[maxn*30];
int rt[maxn];
int cnt=0;
void update(int &x,int y,int l,int r,int index){
T[++cnt]=T[y];
T[cnt].cnt++;
x=cnt;
if(l==r)
return;
int mid=(l+r)>>1;
if(index<=mid)
update(T[x].l,T[y].l,l,mid,index);
else
update(T[x].r,T[y].r,mid+1,r,index);
}
int query(int x,int y,int l,int r,int k){
if(l==r)
return l;
int mid=(l+r)>>1;
int ans=-1;
if(k<=mid&&T[T[y].l].cnt) ans=query(T[x].l,T[y].l,l,mid,k);
if(ans!=-1) return ans;
if(T[T[y].r].cnt) ans=query(T[x].r,T[y].r,mid+1,r,k);
return ans;
}
void input(){
int i;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
for(i=1;i<=n;i++)
update(rt[i],rt[i-1],1,n,a[n-i+1]);
}
void solve(){
int i;
int opt;
int t1,t2;
int ans=0;
set <int>st;
for(i=1;i<=m;i++)
{
scanf("%d",&opt);
if(opt==1){
scanf("%d",&t1);
t1=ans^t1;
st.insert(a[t1]);
}
else{
scanf("%d%d",&t1,&t2);
t1=t1^ans;
t2=t2^ans;
ans=query(rt[1],rt[n-t1],1,n,t2);
if(ans==-1)
ans=n+1;
set<int>::iterator it=st.lower_bound(t2);
if(it!=st.end())
ans=min(ans,*it);
printf("%d\n",ans);
}
}
}
int main(){
int t;
scanf("%d",&t);
while(t--){
cnt=0;
input();
solve();
}
} 1003 K-th occurrence
题目链接
题意：给定一个字符串，区间[l,r]为一个子字符串，寻找这个字符串出现在这个字符串的第k次下标。
思路：用后缀数组跑字符串，二分字符串上下lcp边界，再在这个区间静态求第k大。
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
const int maxasc=128;
int n,q;
char s[maxn];
struct SA {
int t1[maxn], t2[maxn], c[maxn];
int sa[maxn];
int Rank[maxn];
int height[maxn];
int str[maxn];
int n, m;
void init(char *s, int m, int n) {
this->m = m;
this->n = n;
for (int i = 0; i < n; ++i) str[i] = s[i];
str[n] = 0;
}
bool cmp(int *r, int a, int b, int l) {
return r[a] == r[b] && r[a + l] == r[b + l];
}
void work() {
++n;
int i, j, p, *x = t1, *y = t2;
for (i = 0; i < m; ++i) c[i] = 0;
for (i = 0; i < n; ++i) c[x[i] = str[i]]++;
for (i = 1; i < m; ++i) c[i] += c[i - 1];
for (i = n - 1; i >= 0; --i) sa[--c[x[i]]] = i;
for (j = 1; j <= n; j <<= 1) {
p = 0;
//直接利用sa数组排序第二关键字
//后面的j个数第二关键字为空的最小
for (i = n - j; i < n; ++i) {
y[p++] = i;
}
for (i = 0; i < n; ++i) if (sa[i] >= j) y[p++] = sa[i] - j;
//这样数组y保存的就是按照第二关键字排序的结果
//基数排序第一关键字
for (i = 0; i < m; ++i) c[i] = 0;
for (i = 0; i < n; ++i) c[x[y[i]]]++;
for (i = 1; i < m; ++i) c[i] += c[i - 1];
for (i = n - 1; i >= 0; --i) sa[--c[x[y[i]]]] = y[i];
//根据sa和x数组计算新的x数组
swap(x, y);
p = 1; x[sa[0]] = 0;
for (i = 1; i < n; ++i) {
x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++;
}
if (p >= n) break;
//下次基数排序的最大值
m = p;
}
int k = 0;
--n;
for (i = 0; i <= n; ++i) Rank[sa[i]] = i;
//NOild height
for (i = 0; i < n; ++i) {
if (k) --k;
j = sa[Rank[i] - 1];
while (str[i + k] == str[j + k]) ++k;
height[Rank[i]] = k;
}
}
struct RMQ {
int Min[maxn][30];
int mm[maxn];
void init(int n, int *b) {
mm[0] = -1;
for (int i = 1; i <= n; ++i) {
mm[i] = ((i & (i - 1)) == 0) ? mm[i - 1] + 1 : mm[i - 1];
Min[i][0] = b[i];
}
for (int j = 1; j <= mm[n]; ++j) {
for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
Min[i][j] = min(Min[i][j - 1], Min[i + (1 << (j - 1))][j - 1]);
}
}
}
int queryMin(int x, int y) {
int k = mm[y - x + 1];
return min(Min[x][k], Min[y - (1 << k) + 1][k]);
}
}rmq;
void initrmq() {
rmq.init(n, height);
}
int lcp(int x, int y) {
if (x == y) return 1e9;
if (x > y) swap(x, y);
++x;
return rmq.queryMin(x, y);
}
}sa;
int len;
int L,R;
bool check(int mid,int x){
if(sa.lcp(mid,x)>=len)
return 1;
else
return 0;
}
int sorted[maxn];
int num[20][maxn];
int val[20][maxn];
void Build(int l,int r,int level){
if(l==r)return;
int i;
int mid=(l+r)>>1;
int isame=mid-l+1;
for(i=l;i<=r;i++)
if(val[level][i]<sorted[mid])
isame--;
int ln=l,rn=mid+1;
for(i=l;i<=r;i++){
if(i==l)
num[level][i]=0;
else
num[level][i]=num[level][i-1];
//判断数放入左结点或者右结点
if(val[level][i]<sorted[mid] || val[level][i]==sorted[mid]&&isame>0){
val[level+1][ln++]=val[level][i];
num[level][i]++;
if(val[level][i]==sorted[mid])
isame--;
}else{
val[level+1][rn++]=val[level][i];
}
}
Build(l,mid,level+1);
Build(mid+1,r,level+1);
}
int check(int level,int L,int R,int l,int r,int k){
if(l==r)
return val[level][l];
int leftNum,rightNum,totalNum;
if(L==l) leftNum=0;
else leftNum=num[level][L-1];
rightNum=num[level][R];
totalNum=rightNum-leftNum;
int mid=(l+r)>>1;
if(totalNum>=k){
return check(level+1,l+leftNum,l+rightNum-1,l,mid,k);
}else{
int rightindex=mid+1+(L-l-leftNum);
return check(level+1,rightindex,rightindex+R-L-totalNum,mid+1,r,k-totalNum);
}
}
void solve(){
scanf("%d%d",&n,&q);
scanf("%s",s);
sa.init(s,maxasc,n);
sa.work();
sa.initrmq();
// for(int i=1;i<=n;i++)
// cout<<sa.sa[i]<<endl;
// cout<<endl;
int i;
for(i=1;i<=n;i++){
val[0][i]=sa.sa[i];
sorted[i]=sa.sa[i];
}
sort(sorted+1,sorted+1+n);
Build(1,n,0);
int l,r,k;
for(i=0;i<q;i++){
scanf("%d%d%d",&l,&r,&k);
len=r-l+1;
L=1;R=sa.Rank[l-1];
int left,right;
while(L<=R){
int mid=(L+R)>>1;
if(check(mid,sa.Rank[l-1]))
R=mid-1;
else
L=mid+1;
}
left=L;
L=sa.Rank[l-1];R=n;
while(L<=R){
int mid=(L+R)>>1;
if(check(mid,sa.Rank[l-1]))
L=mid+1;
else
R=mid-1;
}
right=R;
// cout<<left<<' '<<right<<endl;
if(right-left+1<k)
printf("-1\n");
else
printf("%d\n",check(0,left,right,1,n,k)+1);
// for(int j=left;j<=right;j++)
// cout<<sa.sa[j]<<endl;
}
}
int main() {
int t;
scanf("%d",&t);
while(t--){
// input();
solve();
}
}
1004 path
题目链接
题意：给你一张图，求图中的第k小路径
思路：1、记录最大的maxk，然后维护一个大小为maxk的multiset。2、BFS加上优先队列，维护扩展点最小出边和当前点的下一条边。
#include <bits/stdc++.h>
#include <set>
#include <vector>
#define maxn 50005
typedef long long ll;
using namespace std;
int n,m,q;
ll ans[maxn];
struct edge{
ll to,cost;
};
bool operator <(const edge &a,const edge &b){
return a.cost<b.cost;
}
vector<edge> G[maxn];
int k[maxn];
int maxK;
multiset <edge>st;
void input(){
scanf("%d%d%d",&n,&m,&q);
int i,j;
ll u,v,w;
maxK=0;
for(i=1;i<=n;i++)
G[i].clear();
st.clear();
for(i=1;i<=m;i++)
{
scanf("%lld%lld%lld",&u,&v,&w);
G[u].push_back((edge){v,w});
}
for(i=1;i<=q;i++){
scanf("%d",&k[i]);
maxK=max(maxK,k[i]);
}
for(i=1;i<=n;i++){
sort(G[i].begin(),G[i].end());
for(j=0;j<G[i].size();j++){
if(st.size()>=maxK)
{
auto it=st.end();
it--;
if(G[i][j].cost>=(*it).cost)
break;
else
st.erase(it);
}
st.insert(G[i][j]);
}
}
}
void solve(){
int i,j;
for(i=1;i<=maxK;i++){
auto it=st.begin();
ans[i]=(*it).cost;
if(i==maxK)break;
ll v=(*it).to;
ll w=(*it).cost;
st.erase(st.begin());
int len=G[v].size();
for(j=0;j<len;j++){
edge temp=(edge){G[v][j].to,G[v][j].cost+w};
if(st.size()>=maxK-i+1)
{
auto it=st.end();
it--;
if(temp.cost>=(*it).cost)
break;
else
st.erase(it);
}
st.insert(temp);
}
}
for(i=1;i<=q;i++)
printf("%lld\n",ans[k[i]]);
}
int main(){
int t;
scanf("%d",&t);
while(t--){
input();
solve();
}
}1006 Shuffle Card
题目链接
题意：刚开始n张牌，m次操作将值为x的拿出来放在最前头，求最后顺序
思路：先从后往前跑m次查询，再跑n的原序列。标记值出现过的不用再出现。栈思想
#include <bits/stdc++.h>
#define maxn 100005
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
int n,m;
int a[maxn];
int b[maxn];
int book[maxn];
void input(){
scanf("%d%d",&n,&m);
int i;
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
for(i=1;i<=m;i++){
scanf("%d",&b[i]);
}
}
void solve(){
int i;
for(i=m;i>=1;i--){
if(!book[b[i]])
{
printf("%d ",b[i]);
book[b[i]]=1;
}
}
for(i=1;i<=n;i++){
if(!book[a[i]])
{
printf("%d ",a[i]);
book[a[i]]=1;
}
}
}
int main(){
input();
solve();
} 1007 Windows Of CCPC
题目链接
题意：给出1阶CCPC的图案。之后每一阶图案的左上、右上、右下都是上一阶图案的复制，左下是上一阶图案的取反。求第k阶图案
思路：分形，暴力
#include <bits/stdc++.h>
#define maxn 1500
typedef long long ll;
using namespace std;
int t;
int n;
char g[11][maxn][maxn];
void input(){
scanf("%d",&n);
}
void solve(){
g[1][1][1]='C';
g[1][1][2]='C';
g[1][2][1]='P';
g[1][2][2]='C';
int cnt,i,j;
for(cnt=2;cnt<=10;cnt++){
int len=pow(2,cnt-1);
for(i=1;i<=len;i++){
for(j=1;j<=len;j++){
g[cnt][i][j]=g[cnt-1][i][j];
}
}
for(i=1;i<=len;i++){
for(j=1;j<=len;j++){
g[cnt][i][j+len]=g[cnt-1][i][j];
}
}
for(i=1;i<=len;i++){
for(j=1;j<=len;j++){
if(g[cnt-1][i][j]=='C')
g[cnt][i+len][j]='P';
else
g[cnt][i+len][j]='C';
}
}
for(i=1;i<=len;i++){
for(j=1;j<=len;j++){
g[cnt][i+len][j+len]=g[cnt-1][i][j];
}
}
}
int L=pow(2,n);
for(i=1;i<=L;i++){
for(j=1;j<=L;j++)
printf("%c",g[n][i][j]);
printf("\n");
}
}
int main(){
scanf("%d",&t);
while(t--){
input();
solve();
}
} 1008 Fishing Master
题目链接
题意：有n条鱼。每条鱼抓需要k的时间，炖需要t[i]的时间，只有抓完鱼才可以炖，求最小时间。
思路：我们需要花费的时间是，抓第一条鱼的时间k+所有鱼炖的时间+前m条鱼抓和炖之间的空隙时间
#include <bits/stdc++.h>
#define maxn 100005
typedef long long ll;
using namespace std;
int t[maxn];
int n,k;
bool cmp(int a,int b){
return a>b;
}
void input(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d",&t[i]);
}
}
void solve(){
ll ans=k;
ll tot=0;
vector <int>v;
for(int i=1;i<=n;i++){
ans+=t[i];
v.push_back(t[i]%k);
tot+=t[i]/k;
}
sort(v.begin(),v.end(),cmp);
int cnt=0;
while(tot<n-1){
ans+=k-v[cnt];
cnt++;
tot++;
}
printf("%lld\n",ans);
}
int main(){
int t;
scanf("%d",&t);
while(t--){
input();
solve();
}
}
/*
2
3 5
20 4 3
*/
京公网安备 11010502036488号