突然想起来没给之前的网络赛留档QAQ
趁着账号没过期赶紧补档
比赛地址
[A]^&^
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int main(){
int T;
cin >> T;
long long int a, b, c = 0;
while(T--) {
cin >> a >> b;
cout << max(1LL, (a&b)) << endl;
}
return 0;
}
[C]K-th occurrence
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
using namespace std;
#define N 100010
#define INF 0x3f3f3f3f
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
const int MAXN = 200005;
char str[MAXN];
int SA[MAXN], srank[MAXN], Height[MAXN], tax[MAXN], tp[MAXN], a[MAXN];
int h[MAXN][30], rmqa[MAXN], rmqn;
int root[N], PHSrank[N];
int n, tot, m;
struct Data {
int x, id;
}A[N];
struct Tree {
int l, r, sum;
}t[N*32];
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &x,int &y){x^=y^=x^=y;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}
inline bool cmp2(Data x,Data y){return x.x<y.x;}
inline void Insert(int &x,int l,int r, int i){
int mid=(l+r)>>1;
t[tot]=t[x];
x=tot;
tot++;
t[x].sum++;
if (l==r) return;
if (PHSrank[i]<=mid) Insert(t[x].l,l,mid,i);
else Insert(t[x].r,mid+1,r,i);
}
inline int Ask(int i,int j,int k,int l,int r){
int mid=0,p=0;
if (l==r) return l;
p=t[t[j].l].sum-t[t[i].l].sum;
mid=(l+r)>>1;
if (k<=p) return Ask(t[i].l,t[j].l,k,l,mid);
else return Ask(t[i].r,t[j].r,k-p,mid+1,r);
}
//srank[i] 第i个后缀的排名;
//SA[i] 排名为i的后缀位置;
//Height[i] 排名为i的后缀与排名为(i-1)的后缀的LCP
void PreProcess() {
int i, j, l;
for (i = 0; i < rmqn; i++) h[i][0] = rmqa[i];
for (j = 1, l = 1; l*2 <= n; j++, l*=2) for (i = 0; i <= n-l*2; i++)
h[i][j] = (h[i][j-1]<h[i+l][j-1]) ? h[i][j-1] : h[i+l][j-1];
}
int Query(int be, int ed) {
int j = 0, l = 1;
while(2*l <= ed-be+1) {j++; l*=2;}
return min(h[be][j], h[ed+1-l][j]);
}
void RSort() {
for (int i = 0; i <= m; i ++) tax[i] = 0;
for (int i = 1; i <= n; i ++) tax[srank[tp[i]]] ++;
for (int i = 1; i <= m; i ++) tax[i] += tax[i-1];
for (int i = n; i >= 1; i --) SA[tax[srank[tp[i]]] --] = tp[i];
}
int cmp(int *f, int x, int y, int w) { return f[x] == f[y] && f[x + w] == f[y + w]; }
void Suffix() {
for (int i = 1; i <= n; i ++) srank[i] = a[i], tp[i] = i;
m = 127 ,RSort();
for (int w = 1, p = 1, i; p < n; w += w, m = p) {
for (p = 0, i = n - w + 1; i <= n; i ++) tp[++ p] = i;
for (i = 1; i <= n; i ++) if (SA[i] > w) tp[++ p] = SA[i] - w;
RSort(), swap(srank, tp), srank[SA[1]] = p = 1;
for (i = 2; i <= n; i ++) srank[SA[i]] = cmp(tp, SA[i], SA[i - 1], w) ? p : ++ p;
}
int j, k = 0;
for(int i = 1; i <= n; Height[srank[i ++]] = k)
for( k = k ? k - 1 : k, j = SA[srank[i] - 1]; a[i + k] == a[j + k]; ++ k);
}
void Init() {
scanf("%s", str);
n = strlen(str);
for (int i = 0; i < n; i ++) a[i + 1] = str[i];
}
int findrmq(int l, int r) {
if (l > r) return 0;
if (l == r) return MAXN;
int left = l+1, right = r;
return Query(left-2, right-2);
}
int find1(int ll, int rr, int k) {
int l = ll, r = rr;
while(r > l) {
int mid = (l+r) >> 1;
if (findrmq(mid, rr) >= k) r = mid;
else l = mid+1;
}
return l;
}
int find2(int ll, int rr, int k) {
int l = ll, r = rr;
while(r > l) {
int mid = ((l+r) >> 1) + 1;
if (findrmq(ll, mid) >= k) l = mid;
else r = mid-1;
}
return l;
}
int ask(int l, int r, int k) {
return A[Ask(root[l-1], root[r], k, 1, n)].x;
}
int main() {
//freopen("1.txt", "r", stdin);
int T; cin >> T;
while(T--) {
int len, q; scanf("%d%d", &len, &q);
n = len;
memset(SA, 0, sizeof(SA));
memset(srank, 0, sizeof(srank));
memset(Height, 0, sizeof(Height));
memset(tax, 0, sizeof(tax));
memset(tp, 0, sizeof(tp));
memset(a, 0, sizeof(a));
Init();
Suffix();
for (int i = 0; i < n-1; i++) rmqa[i] = Height[i+2];
rmqn = len-1;
PreProcess();
for (int i = 1; i <= n; i++) { A[i].x = SA[i]; A[i].id = i; }
sort(A+1, A+1+n, cmp2);
for (int i = 1; i <= n; i++) PHSrank[A[i].id] = i;
tot = 1;
for (int i = 1; i <= n; i++) {
root[i] = root[i-1];
Insert(root[i], 1, n, i);
}
/*
cout << "srank : \n" ;
for (int i = 1; i <= n; i++) printf("%2d ", srank[i]);
cout << endl;
cout << "SA : \n";
for (int i = 1; i <= n; i++) printf("%2d ", SA[i]);
cout << endl;
cout << "Height : \n";
for (int i = 1; i <= n; i++) printf("%2d ", Height[i]);
cout << endl;
cout << "rmq : \n";
for (int i = 0; i < rmqn; i++) printf("%2d ", rmqa[i]);
cout << endl;*/
for (int i = 1; i <= q; i++) {
int l, r, k;
scanf("%d%d%d", &l, &r, &k);
int ll = find1(1, srank[l], r-l+1);
int rr = find2(srank[l], len, r-l+1);
if (rr - ll + 1 < k) cout << "-1" << endl;
else cout << ask(ll, rr, k) << endl;
}
}
}
[F]Shuffle Card
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define N 200010
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int n,m,i,top,x,p,q;
int a[N],tail[N],head[N];
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline LL Min(LL a,LL b){return (a<b)?a:b;}
inline LL Max(LL a,LL b){return (a>b)?a:b;}
inline int read(){
int p=0; char c=getchar();
while (c<48||c>57) c=getchar();
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p;
}
int main(){
scanf("%d%d",&n,&m);
if (n==1){
printf("1\n");
return 0;
}
for (i=1;i<=n;i++) scanf("%d",&a[i]);
if (m==0){
for (i=1;i<=n;i++)
printf("%d ",a[i]);
}
for (i=1;i<=n;i++){
head[a[i]]=a[i-1]; tail[a[i]]=a[i+1];
}
head[a[1]]=0; tail[a[n]]=0;
top=a[1];
for (i=1;i<=m;i++){
scanf("%d",&x);
if (x==top) continue;
p=head[x]; q=tail[x];
tail[p]=q; head[q]=p;
head[top]=x; tail[x]=top;
head[x]=0; top=x;
}
for (i=top;i;i=tail[i])
printf("%d ",i);
return 0;
}
[G]Windows Of CCPC
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int s[2050][2050], T, n;
int main(){
int T;
cin >> T;
s[1][1] = 1;
s[1][2] = 1;
s[2][1] = -1;
s[2][2] = 1;
for (int i = 2; i <= 1024; i*=2) {
for (int a = 1; a <= i; a++) for (int b = 1; b <= i; b++) {
s[a][b+i] = s[a+i][b+i] = s[a][b];
s[a+i][b] = -1 * s[a][b];
}
}
while(T--) {
scanf("%d", &n);
for (int i = 1; i <= (1<<n); i++) {
for (int j = 1; j <= (1<<n); j++)
if (s[i][j] == 1) printf("C");
else printf("P");
cout << endl;
}
}
return 0;
}
[H]Fishing Master
#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#define IL inline
#define LL long long
#define ULL unsigned LL
#define _BS 1048576
char _bf[_BS];
char *__p1=_bf,*__p2=_bf;
#define _IO char *_p1=__p1,*_p2=__p2;
#define _OI __p1=_p1,__p2=_p2;
#ifdef _KEVIN
#define GC getchar()
#else
#define GC (_p1==_p2&&(_p2=(_p1=_bf)+fread(_bf,1,_BS,stdin),_p1==_p2)?EOF:*_p1++)
#endif
#define PC putchar
#define _Q_(x) {register char _c=GC,_v=1;for(x=0;_c<48||_c>57;_c=GC)if(_c==45)_v=-1;
#define _H_(x) for(;_c>=48&&_c<=57;x=(x<<1)+(x<<3)+_c-48,_c=GC);if(_v==-1)x=-x;}
#define sc(x) _Q_(x)_H_(x)
#define se(x) _Q_(x)else if(_c==EOF)return 0;_H_(x)
#define _G1(_1) int _1;sc(_1)
#define _G2(_1,_2) int _1,_2;sc(_1)sc(_2)
#define _G3(_1,_2,_3) int _1,_2,_3;sc(_1)sc(_2)sc(_3)
#define _gG(_1,_2,_3,_get, ...) _get
#define get(...) _gG(__VA_ARGS__,_G3,_G2,_G1, ...)(__VA_ARGS__)
#define F(i,l,r) for(int i=(l);i<(r);++i)
template<class T>
void UPRT(const T _){if(_>=10)UPRT(_/10);PC(_%10+48);}
#define UPL(_) UPRT(_),PC(10)
template<class T>
void PRT(const T _){if(_<0){PC(45),UPRT<ULL>(-(ULL)_);return;}if(_>=10)PRT(_/10);PC(_%10+48);}
#define PL(_) PRT(_),PC(10)
#define MN 1000007
int res[MN], rnt;
int main()
{
_IO
int cnt, ti, r;
LL sum, more;
get(T)while (T--)
{
sum = more = 0;
cnt = rnt = 0;
get(n, k)
for (int i=0; i<n; ++i)
{
sc(ti)
sum += ti;
r = ti % k;
if (r)
res[rnt++] = r;
cnt += ti / k;
}
if (cnt >= n-1)
more = 0;
else
{
std::sort(res, res+rnt, std::greater<int>());
int resn = n-1 - cnt;
for (int i=0; i<resn; ++i)
more += k-res[i];
}
PL(sum + k + more);
}
return 0;
}
声明:
本文采用
BY-NC-SA
协议进行授权，如无注明均为原创，转载请注明转自
Marvolo
本文地址: 2019CCPC网络赛
本文地址: 2019CCPC网络赛
