The Preliminary Contest for ICPC Asia Xuzhou 2019
A Math Problem
题目链接
题意：裸的 扩展欧几里得+斐波那契博弈
思路：模板题
#include <bits/stdc++.h>
#define maxn 15
typedef long long ll;
using namespace std;
int n;
ll GCD;
ll bi[maxn],ai[maxn];
ll gcd(ll a,ll b) {while(b^=a^=b^=a%=b);return a;}
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==0){x=1;y=0;return a;}
ll gcd=exgcd(b,a%b,x,y);
ll tp=x;
x=y; y=tp-a/b*y;
return gcd;
}
ll qmul(ll a,ll b,ll m){
ll ans=0;
ll k=a;
ll f=1;//f是用来存负号的
if(k<0){f=-1;k=-k;}
if(b<0){f*=-1;b=-b;}
while(b){
if(b&1)
ans=(ans+k)%m;
k=(k+k)%m;
b>>=1;
}
return ans*f;
}
ll excrt()
{
ll x,y,k;
ll M=bi[1],ans=ai[1];
//bi被余数，ai余数
for(int i=2;i<=n;i++)
{
ll a=M,b=bi[i],c=(ai[i]-ans%b+b)%b;
ll gcd=exgcd(a,b,x,y),bg=b/gcd;
if(c%gcd!=0) return -1;
x=qmul(x,c/gcd,bg);//快乘
ans+=x*M;
M*=bg;
ans=(ans%M+M)%M;
}
return (ans%M+M)%M;
}
void input(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lld%lld",&bi[i],&ai[i]);
if(i==1)
GCD=bi[i];
else
GCD=GCD*bi[i]*gcd(GCD,bi[i]);
}
}
vector <ll>fab;
void solve(){
ll ans=excrt();
// cout<<ans<<endl;
if(ans!=-1){
if(ans<=1)
ans=GCD+ans;
fab.push_back(1);
fab.push_back(2);
int i=2;
int flag=0;
if(ans==1||ans==2)
flag=1;
while(fab[i-2]+fab[i-1]<=ans){
if(fab[i-2]+fab[i-1]==ans){
flag=1;
break;
}
fab.push_back(fab[i-2]+fab[i-1]);
i++;
}
if(flag)
printf("Lbnb!\n");
else
printf("Zgxnb!\n");
}else
printf("Tankernb!\n");
}
int main(){
input();
solve();
} B so easy
题目链接
题意：1-n一共n个值，操作1、选择一个数，使其不可用。操作2、查找一个数，它或者它之后第一个可用的数
思路：并查集连接可行、不可行，通过unordered_map维护
#include <bits/stdc++.h>
using namespace std;
int n, q;
int u, v;
unordered_map <int, int>ma;
int find(int x) {
if (!ma.count(x)) {
return x;
}
else
return ma[x] = find(ma[x]);
}
void mix(int x, int y) {
int fx = find(x);
int fy = find(y);
ma[fx] = fy;
}
void input() {
scanf("%d%d", &n, &q);
for (int i = 1; i <= q; i++) {
scanf("%d%d", &u, &v);
if (u == 1)
ma[v] = find(v + 1);
else {
int tmp = find(v);
if (tmp > n)puts("-1");
else printf("%d\n", tmp);
}
}
}
int main() {
input();
// solve();
}
C Buy Watermelon
题目链接
题意：给定w表示西瓜重量，切成两半，要求每一部分都是2的倍数，输出yes、no
思路：签到
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<string>
#include<cmath>
#include<stack>
#include<functional>
#include<bitset>
#define ll long long
#define maxn 100002
const int INF = 0x3f3f3f3f;
using namespace std;
int main(void){
int a;
scanf("%d",&a);
if(a % 2 == 0&&a > 2){
puts("YES");
}
else{
puts("NO");
}
return 0;
} D Carneginon
题目链接
KMP相关，zl所A。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<string>
#include<cmath>
#include<stack>
#include<functional>
#include<bitset>
#define ll long long
#define maxn 100002
const int INF = 0x3f3f3f3f;
using namespace std;
char x[maxn], y[maxn], z[maxn];
int nextt[maxn], ans[maxn];
int m, n;
void prekmp() {
int i, j;
j = nextt[0] = -1;
i = 0;
while (i < m) {
while (j != -1 && x[i] != x[j]) {
j = nextt[j];
}
if (x[++i] == x[++j]) {
nextt[i] = nextt[j];
}
else {
nextt[i] = j;
}
}
}
int kmp() {
prekmp();
int i, j, answer;
i = j = answer = 0;
while (i < n) {
while (j != -1 && x[j] != y[i]) {
j = nextt[j];
}
i++;
j++;
if (j == m) {
j = nextt[j];
ans[answer++] = i;
}
}
return answer;
}
void prekmp1() {
int i, j;
j = nextt[0] = -1;
i = 0;
while (i < n) {
while (j != -1 && y[i] != y[j]) {
j = nextt[j];
}
if (y[++i] == y[++j]) {
nextt[i] = nextt[j];
}
else {
nextt[i] = j;
}
}
}
int kmp1() {
prekmp1();
int i, j, answer;
i = j = answer = 0;
while (i < m) {
while (j != -1 && y[j] != x[i]) {
j = nextt[j];
}
i++;
j++;
if (j == n) {
j = nextt[j];
ans[answer++] = i;
}
}
return answer;
}
int main(void) {
int t, i, q, len1, len, num;
scanf("%s", y);
scanf("%d", &q);
n = len = strlen(y);
while (q--) {
scanf("%s", x);
m = len1 = strlen(x);
if (len1 < len) {
num = kmp();
if (num) {
puts("my child!");
}
else {
puts("oh, child!");
}
}
else if (len1 > len) {
num = kmp1();
if (num) {
puts("my teacher!");
}
else {
puts("senior!");
}
}
else {
num = 1;
for (i = 0; i < len; i++) {
if (x[i] != y[i]) {
num = 0;
break;
}
}
if (num) {
puts("jntm!");
}
else {
puts("friend!");
}
}
}
return 0;
} E XKC's basketball team
题目链接
题意：对于每个数求，比它大m且最远的位置
思路：线段树暴力
#include <bits/stdc++.h>
#define maxn 500005
using namespace std;
int n, m;
int a[maxn];
int maxx[maxn << 2];
void PushUp(int rt) {
maxx[rt] = max(maxx[rt << 1], maxx[rt << 1 | 1]);
}
void Build(int l, int r, int rt) {
if (l == r)
{
maxx[rt] = a[l];
return;
}
int mid = (l + r) >> 1;
Build(l, mid, rt << 1);
Build(mid + 1, r, rt << 1 | 1);
PushUp(rt);
}
int query(int val, int l, int r, int rt) {
//cout << val << " " << l << " " << r << endl;
if (l == r)
return l;
int mid = (l + r) >> 1;
if (maxx[rt << 1 | 1] >= val)
return query(val, mid + 1, r, rt << 1 | 1);
if (maxx[rt << 1] >= val)
return query(val, l, mid, rt << 1);
return -1;
}
void input() {
scanf("%d%d", &n, &m);
int i;
for (i = 1; i <= n; i++)
scanf("%d", &a[i]);
}
int isk = 0;
void p(int x) {
if (!isk) {
isk = 1;
printf("%d", x);
}
else
printf(" %d", x);
}
void solve() {
isk = 0;
Build(1, n, 1);
int i;
for (i = 1; i <= n; i++) {
int ANS = query(a[i] + m, 1, n, 1);
if (ANS <= i)p(-1);
else p(ANS-i-1);
}
}
int main() {
input();
solve();
} G Colorful String
题目链接
回文树相关，lzk所A
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 3e5 + 10;
ll ans;
struct PAM {//回文树
set<int>cor[maxn];
int num[maxn];
// 一个结点一个本质不同的回文串
int next[maxn][26];// next[i][c]编号为i的节点表示的回文串在两边添加字符c以后变成的回文串的编号（儿子）。
int fail[maxn];// fail[i] 节点i失配以后跳转不等于自身的节点i表示的回文串的最长后缀回文串
int len[maxn];//len[i] 表示回文串i的长度
int cnt[maxn];//cnt[i] 节点i表示的本质不同的串的个数
int S[maxn];// S[i] 第i次添加的字符（一开始设S[0] = -1，也可以是任意一个在串S中不会出现的字符）
//（建树时求出的不是完全的，最后重新统计一遍以后才是正确的）。
int id;//2~id-1 添加的结点 n 添加的字符个数
int n, last;//last 新添加一个字母后所形成的最长回文串表示的节点
int newnode(int x) {
for (int i = 0; i<26; i++) {
next[id][i] = 0;
}
num[id] = 0;
cnt[id] = 0;
len[id] = x;
cor[id].clear();
return id++;
}
void init(int le) {
memset(cnt, 0, sizeof(cnt));
id = 0;
newnode(0);
newnode(-1);
fail[0] = 1;
S[0] = -1;
last = n = 0;
}
int getfail(int x) {
while (S[n - len[x] - 1] != S[n]) x = fail[x];
return x;
}
void Insert(int c) {
c -= 'a';
S[++n] = c;
int cur = getfail(last);
if (!next[cur][c]) {
int now = newnode(len[cur] + 2);
fail[now] = next[getfail(fail[cur])][c];
next[cur][c] = now;
//
num[now] = num[fail[now]] + 1;
}
last = next[cur][c];
cor[last] = cor[cur];
//cout << c << endl;
cor[last].insert(c);
cnt[last]++;
}
void getAns() {//自下向上更新
for (int i = id - 1; i >= 0; i--) {
cnt[fail[i]] += cnt[i];
ans += 1ll * cnt[i] * ((int)cor[i].size());
//cout << "i: " << i << " cnt[i]:" << cnt[i] << " cor.size(): " << cor[i].size() << endl;
}
}
}pam;
char s[maxn];
int main() {
while (~scanf("%s", s)) {
ans = 0;
int len = strlen(s);
pam.init(len);
for (int i = 0; i < len; i++) {
pam.Insert(s[i]);
}
pam.getAns();
printf("%lld\n", ans);
}
} I query
题目链接
题意：给定一个数列，求区间[l,r]包含多少个min(pi,pj)=gcd(pi,pj)
思路：nlogn找出倍数关系，然后下标离散，建立主席树
#include <bits/stdc++.h>
#define maxn 1000005
#define N 100005
typedef long long ll;
using namespace std;
int n,m;
int a[N];
int ind[N];
struct node{
int l,r;
int cnt;
node(){
l=r=cnt=0;
}
}T[maxn*18];
int rt[maxn];
int xCopy[maxn];
int tot=0;
int ans=0;
inline void update(int &x,int y,int l,int r,int pos,int val){
T[++tot]=T[y];
T[tot].cnt+=val;
x=tot;
if(l==r)return;
int mid=(l+r)>>1;
if(pos<=mid)
update(T[x].l,T[y].l,l,mid,pos,val);
else
update(T[x].r,T[y].r,mid+1,r,pos,val);
}
inline void query(int x,int y,int l,int r,int L,int R){
if (L <= l && r <= R) {
ans += T[y].cnt - T[x].cnt;
return;
}
int mid = l + r >> 1;
if (L <= mid)query(T[x].l, T[y].l, l, mid, L, R);
if (R > mid)query(T[x].r, T[y].r, mid + 1, r, L, R);
}
inline void input(){
scanf("%d%d",&n,&m);
int i,j;
int IND;
for(i=1;i<=n;++i){
scanf("%d",&a[i]);
// a[i] = i;
if(a[i]==1)
IND=i;
ind[a[i]]=i;
}
int cnt=1,tmp;
for(i=1;i<=n;++i){
if(a[i]>n/2||a[i]==1)continue;
tmp=a[i];
for(j=tmp*2;j<=n;j+=tmp){
update(rt[cnt],rt[cnt-1],1,n,ind[j],1);
xCopy[cnt]=ind[a[i]];
// cout<<ind[a[i]]<<endl;
++cnt;
}
}
// cout<<cnt<<endl;
// for(i=1;i<cnt;i++)
// cout<<xCopy[i]<<endl;
int x,y,pos1,pos2;
for(i=1;i<=m;++i){
scanf("%d%d",&x,&y);
pos1=lower_bound(xCopy+1,xCopy+cnt,x)-xCopy;
pos2=upper_bound(xCopy+1,xCopy+cnt,y)-xCopy-1;
// cout<<"!"<<pos1<<" "<<pos2<<endl;
ans=0;
query(rt[pos1-1],rt[pos2],1,n,x,y);
if(x<=IND&&IND<=y)
ans+=y-x;
printf("%d\n",ans);
}
}
int main(){
input();
}
/*
5 100
5 4 3 2 1
5 100
4 1 3 2 5
*/做法是，将询问和更新都变为[l,r]形式的二元组存储，对于这样二元组排序，先按右区间排序，保证区间尽量靠左端，再按左区间排序保证区间尽量小，最后保证询问再更新之后。树状数组维护二维偏序关系。
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
int n,m;
int a[maxn];
int ind[maxn];
int ans[maxn];
int c[maxn];
struct node{
int flag;
int id;
int l,r;
};
vector <node>v;
int lowbit(int x){
return x&(-x);
}
void add(int i,int val){
while(i<=n){
c[i]+=val;
i+=lowbit(i);
}
}
int sum(int i){
int ans=0;
while(i){
ans+=c[i];
i-=lowbit(i);
}
return ans;
}
bool cmp(node a,node b){
if(a.r==b.r)
{
if(a.l==b.l)
return a.flag<b.flag;
else
return a.l>b.l;
}else
return a.r<b.r;
}
void input()
{
scanf("%d%d",&n,&m);
int i,j;
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
ind[a[i]]=i;
}
for(i=1;i<=n;i++){
for(j=i+i;j<=n;j+=i){
int a=ind[i];
int b=ind[j];
if(a>b)
swap(a,b);
v.push_back((node){1,0,a,b});
}
}
int l,r;
for(i=1;i<=m;i++){
scanf("%d%d",&l,&r);
v.push_back((node){2,i,l,r});
}
sort(v.begin(),v.end(),cmp);
int tot=0;
for(i=0;i<v.size();i++){
if(v[i].flag==1){
add(v[i].l,1);
tot++;
}else
ans[v[i].id]=tot-sum(v[i].l-1);
}
for(int i=1;i<=m;i++)
printf("%d\n",ans[i]);
}
int main(){
input();
// solve();
} J Random Access Iterator
题目链接
树形dp，zl、lzk所A
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
vector<int>v[maxn];
int dep[maxn];
int ans[maxn];
int MA_dep = 0;
void dfs(int x, int fa) {
for (int y : v[x]) {
if (y == fa)continue;
dep[y] = dep[x] + 1;
MA_dep = max(MA_dep, dep[y]);
dfs(y, x);
}
}
ll qpow(ll A, int B) {
ll t = 1;
while (B) {
if ((B & 1)) {
t = t * A%mod;
}
A = A * A%mod;
B = B >> 1;
}
return t;
}
ll dfs1(int x, int fa) {
if (dep[x] == MA_dep) {
return 1LL;
}
ll res = 0;
for (int y : v[x]) {
if (y == fa)continue;
res += dfs1(y, x);
}
int s = v[x].size();
if (x != 1) {
s--;
}
res = res * qpow(s, mod - 2) % mod;
res = (1 - res + mod) % mod;
res = qpow(res, s);
res = (1 - res + mod) % mod;
return res;
}
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i < n; i++) {
int x, y;
scanf("%d%d", &x, &y);
v[x].push_back(y); swap(x, y);
v[x].push_back(y);
}
dep[1] = 1;
dfs(1, -1);
ll ans=dfs1(1, -1);
printf("%lld\n", ans);
} K Center
题目链接
状压dp，规律，zl、lzk所A
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1e3 + 5;
int x[maxn], y[maxn];
const int M = 1e7;
unordered_map<ll, set<int> >mp;
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d%d", &x[i], &y[i]);
}
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j++) {
int xx = x[i] + x[j];
int yy = y[i] + y[j];
ll num = xx * M + yy;
mp[num].insert(i);
mp[num].insert(j);
}
}
for (auto p : mp) {
int sz = (int)p.second.size();
ans = max(ans, sz);
}
printf("%d\n", n - ans);
} M Longest subsequence
题目链接
dp，zl、lzk所A
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<string>
#include<cmath>
#include<stack>
#include<functional>
#include<bitset>
#define ll long long
#define maxn 100002
const int INF = 0x3f3f3f3f;
using namespace std;
int poss[32];
int n, m;
char s[maxn * 10], t[maxn * 10];
int main(void){
int i, j = 0, k, ans = -1;
scanf("%d %d",&n,&m);
scanf("%s %s",s,t);
for(i = 0;i < 26;i++){
poss[i] = -1;
}
for(i = 0;i < n;i++){
for(k = 0;k < s[i] - 'a';k++){
if(poss[k] != -1){
ans = max(ans,n - i + poss[k]);
}
}
if(j == m||s[i] > t[j]){
ans = max(ans,n - i + j);
if(j < m - 1){
j++;
}
}
else if(s[i] == t[j]){
poss[s[i] - 'a'] = j;
j++;
}
}
printf("%d\n",ans);
return 0;
}
/*
3 2
abc
ab
*/
京公网安备 11010502036488号