2017 ACM/ICPC广西邀请赛
A Math Problem
题目链接
题意：给你一个n，求有多少个k满足
思路：预处理
#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;
ll num[22];
int s;
void init(){
ll i, j, t;
s = 1;
for(i = 1;i < 18;i++){
t = 1;
for(j = 0;j < i;j++){
if(1e18 / i >= t){
t *= i;
}
else{
return;
}
}
s = i;
num[i] = t;
}
}
int main(void){
init();
num[s + 1] = 1000000000000000002;
ll n, i;
while(scanf("%lld",&n)!=EOF){
for(i = 0;;i++){
if(n < num[i]){
printf("%lld\n",i - 1);
break;
}
}
}
return 0;
} B Color it
题目链接
题意：四种操作。0、初始化，清除操作。1、在坐标(x,y)上画上颜色c。2、计算(1,y1)到(x,y2)有多少种不同颜色。3、结束
思路：由于只有50种颜色，考虑建50棵线段树。采用动态开点，设立root数组表示第i种颜色的根节点编号。线段树上记录最小值，询问是否存在小于等于x。
#include <bits/stdc++.h>
#define maxn 1000005
using namespace std;
struct node{
int l,r,cnt;
node(){
l=r=cnt=0;
}
}T[maxn<<2];
int rt[55];
int tot=0;
int opr;
void update(int &rt,int l,int r,int pos,int val){
if(!rt){
rt=++tot;
T[rt].l=T[rt].r=0;
T[rt].cnt=val;
}
T[rt].cnt=min(T[rt].cnt,val);
if(l==r)
return;
int mid=(l+r)>>1;
if(pos<=mid) update(T[rt].l,l,mid,pos,val);
else update(T[rt].r,mid+1,r,pos,val);
}
bool query(int rt,int l,int r,int L,int R,int x){
if(!rt)
return false;
if(L<=l&&r<=R){
return T[rt].cnt<=x;
}
int mid=(l+r)>>1;
if(L<=mid&&query(T[rt].l,l,mid,L,R,x))
return true;
if(R>mid&&query(T[rt].r,mid+1,r,L,R,x))
return true;
return false;
}
void input(){
int x,y,c,l,r;
if(opr==0){
memset(rt,0,sizeof rt);
tot=0;
}else if(opr==1){
scanf("%d%d%d",&x,&y,&c);
update(rt[c],1,maxn-1,y,x);
}else if(opr==2){
scanf("%d%d%d",&x,&l,&r);
int ans=0;
for(int i=0;i<=50;i++){
if(query(rt[i],1,maxn-1,l,r,x))
ans++;
}
printf("%d\n",ans);
}
}
//void solve(){
//
//}
int main(){
while(scanf("%d",&opr)!=EOF){
if(opr==3)break;
input();
// solve();
}
} C Counting Stars
题目链接
题意：定义由两个三元环共享一条边的图为星星，求图上有多少子图可以构成星星
思路：对于三元环，有的做法判断。度数大向小连有向边，度数相同则编号小向编号大连有向边，然后对于每条边第第一个顶点的相连点标号，对第二个顶点相连点标号。 若存在一个三元环，将三元环的三边贡献都+1。对于每条边求C(n,2)。
为何是对于每条边求C(n,2)，可能存在两个互不相交的子图都是要求的星型。
#include <bits/stdc++.h>
#define maxn 100005
typedef long long ll;
using namespace std;
int n,m;
int x[maxn<<1],y[maxn<<1];
int deg[maxn];
int vis[maxn];
int ans[maxn<<1];
int pos[maxn];
struct edge{
int to,index;
};
vector <edge>G[maxn];
void input(){
int i;
for(i=1;i<=m;i++){
scanf("%d%d",&x[i],&y[i]);
deg[x[i]]++;
deg[y[i]]++;
}
}
void solve(){
int i,j;
for(i=1;i<=m;i++){
if(deg[x[i]]>deg[y[i]])
G[y[i]].push_back((edge){x[i],i});
else if(deg[x[i]]<deg[y[i]])
G[x[i]].push_back((edge){y[i],i});
else
{
if(x[i]<y[i])
G[x[i]].push_back((edge){y[i],i});
else
G[y[i]].push_back((edge){x[i],i});
}
}
memset(vis,0,sizeof vis);
memset(pos,0,sizeof pos);
memset(ans,0,sizeof ans);
for(i=1;i<=m;i++){
int u=x[i],v=y[i];
for(j=0;j<G[u].size();j++){
vis[G[u][j].to]=i;
pos[G[u][j].to]=G[u][j].index;
}
for(j=0;j<G[v].size();j++)
{
if(vis[G[v][j].to]==i){
ans[i]++;
ans[G[v][j].index]++;
ans[pos[G[v][j].to]]++;
}
}
}
ll ANS=0;
for(i=1;i<=m;i++)
ANS+=1ll*ans[i]*(ans[i]-1)/2;
printf("%lld\n",ANS);
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
for(int i=1;i<=n;i++)
G[i].clear();
memset(deg,0,sizeof deg);
input();
solve();
}
}
/*
8 10
1 2
2 3
3 4
1 4
1 3
5 6
6 7
7 8
5 8
5 7
*/ D Covering
题目链接
题意：给你一个n,求有多少种方式12和21的毯子铺4n的空间
思路：zl递推出规律，建立了1616的矩阵快速幂，T了。用BM线性递推输入数据过了。。
正解的规律是dp[4]=dp[3]+5*dp[2]+dp[1]-dp[0]
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// head
ll _,n;
namespace linear_seq {
const int N=10010;
ll res[N],base[N],_c[N],_md[N];
vector<int> Md;
void mul(ll *a,ll *b,int k) {
rep(i,0,k+k) _c[i]=0;
rep(i,0,k) if (a[i]) rep(j,0,k) _c[i+j]=(_c[i+j]+a[i]*b[j])%mod;
for (int i=k+k-1;i>=k;i--) if (_c[i])
rep(j,0,SZ(Md)) _c[i-k+Md[j]]=(_c[i-k+Md[j]]-_c[i]*_md[Md[j]])%mod;
rep(i,0,k) a[i]=_c[i];
}
int solve(ll n,VI a,VI b) { // a 系数 b 初值 b[n+1]=a[0]*b[n]+...
// printf("%d\n",SZ(b));
ll ans=0,pnt=0;
int k=SZ(a);
assert(SZ(a)==SZ(b));
rep(i,0,k) _md[k-1-i]=-a[i];_md[k]=1;
Md.clear();
rep(i,0,k) if (_md[i]!=0) Md.push_back(i);
rep(i,0,k) res[i]=base[i]=0;
res[0]=1;
while ((1ll<<pnt)<=n) pnt++;
for (int p=pnt;p>=0;p--) {
mul(res,res,k);
if ((n>>p)&1) {
for (int i=k-1;i>=0;i--) res[i+1]=res[i];res[0]=0;
rep(j,0,SZ(Md)) res[Md[j]]=(res[Md[j]]-res[k]*_md[Md[j]])%mod;
}
}
rep(i,0,k) ans=(ans+res[i]*b[i])%mod;
if (ans<0) ans+=mod;
return ans;
}
VI BM(VI s) {
VI C(1,1),B(1,1);
int L=0,m=1,b=1;
rep(n,0,SZ(s)) {
ll d=0;
rep(i,0,L+1) d=(d+(ll)C[i]*s[n-i])%mod;
if (d==0) ++m;
else if (2*L<=n) {
VI T=C;
ll c=mod-d*powmod(b,mod-2)%mod;
while (SZ(C)<SZ(B)+m) C.pb(0);
rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;
L=n+1-L; B=T; b=d; m=1;
} else {
ll c=mod-d*powmod(b,mod-2)%mod;
while (SZ(C)<SZ(B)+m) C.pb(0);
rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;
++m;
}
}
return C;
}
int gao(VI a,ll n) {
VI c=BM(a);
c.erase(c.begin());
rep(i,0,SZ(c)) c[i]=(mod-c[i])%mod;
return solve(n,c,VI(a.begin(),a.begin()+SZ(c)));
}
};
int main() {
while (~scanf("%lld",&n)) {
vector<int>v;
v.push_back(1);//前几项
v.push_back(5);
v.push_back(11);
v.push_back(36);
v.push_back(95);
v.push_back(281);
v.push_back(781);
v.push_back(2245);
v.push_back(6336);
v.push_back(18061);
v.push_back(51205);
v.push_back(145601);
v.push_back(413351);
v.push_back(1174500);
v.push_back(3335651);
v.push_back(9475901);
//输入n ,输出第n项的值
printf("%d\n",linear_seq::gao(v,n-1));
}
}
E CS Course
题目链接
题意：给出n个数字，q次查询，查询除了第ai个数剩余所有数的与值、或值、异或值。
思路：前缀+后缀
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
int n,q;
int a[maxn];
int preand[maxn],sufand[maxn];
int prexor[maxn],sufxor[maxn];
int preor[maxn],sufor[maxn];
void input(){
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
preand[1]=prexor[1]=preor[1]=a[1];
for(int i=2;i<=n;i++){
preand[i]=preand[i-1]&a[i];
prexor[i]=prexor[i-1]^a[i];
preor[i]=preor[i-1]|a[i];
}
sufand[n]=sufxor[n]=sufor[n]=a[n];
for(int i=n-1;i>1;i--){
sufand[i]=sufand[i+1]&a[i];
sufxor[i]=sufxor[i+1]^a[i];
sufor[i]=sufor[i+1]|a[i];
}
}
void solve(){
int i,index;
for(i=1;i<=q;i++){
scanf("%d",&index);
int a=index-1;
int b=index+1;
if(a<1)
printf("%d %d %d\n",sufand[index+1],sufor[index+1],sufxor[index+1]);
else if(b>n)
printf("%d %d %d\n",preand[index-1],preor[index-1],prexor[index-1]);
else
printf("%d %d %d\n",preand[index-1]&sufand[index+1],preor[index-1]|sufor[index+1],prexor[index-1]^sufxor[index+1]);
}
}
int main(){
while(scanf("%d%d",&n,&q)!=EOF){
input();
solve();
}
} F Destroy Walls
题目链接
题意：给出n个城市，存在m座墙，第i座墙连接着ui城市和vi城市，求国王希望到达城市每一个地方所需要的拆墙的最少费用，以及拆多少座
思路：求最大生成树
#include <bits/stdc++.h>
#define maxn 100005
typedef long long ll;
using namespace std;
int n,m;
struct edge{
int from,to,cost;
};
bool cmp(edge a,edge b){
return a.cost>b.cost;
}
edge G[maxn<<1];
int fa[maxn];
ll sum;
void init(int n){
for(int i=1;i<=n;i++)
fa[i]=i;
}
int find(int x){
return x==fa[x]?x:fa[x]=find(fa[x]);
}
void mix(int x,int y){
int fx=find(x);
int fy=find(y);
fa[fx]=fy;
}
void input(){
init(n);
int i,x,y;
for(i=1;i<=n;i++){
scanf("%d%d",&x,&y);
}
int u,v,w;
sum=0;
for(i=1;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
G[i].from=u;
G[i].to=v;
G[i].cost=w;
sum+=G[i].cost;
}
}
void solve(){
sort(G+1,G+1+m,cmp);
ll ans=0;
int tot=0;
for(int i=1;i<=m;i++){
if(find(G[i].from)!=find(G[i].to)){
ans+=G[i].cost;
tot++;
mix(G[i].from,G[i].to);
}
}
printf("%lld %lld\n",m-tot,sum-ans);
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
input();
solve();
}
} G Duizi and Shunzi
题目链接
题意：给出n张牌，求能组成最多的对子或者顺子个数。
思路：对子优于顺子，特判顺子的一种情况
#include <bits/stdc++.h>
#define maxn 1000005
using namespace std;
int n;
int t[maxn];
void input(){
int i,a;
for(i=1;i<=n;i++){
scanf("%d",&a);
t[a]++;
}
}
void solve(){
int ans=0;
int i;
for(i=1;i<=1000000;i++){
if(t[i]>=2){
ans+=t[i]/2;
t[i]=t[i]&1;
}
while(i+2<=1000000&&t[i]&&t[i+1]%2&&t[i+2]){
t[i]--;
t[i+1]--;
t[i+2]--;
ans++;
}
}
printf("%d\n",ans);
}
int main(){
while(scanf("%d",&n)!=EOF){
memset(t,0,sizeof t);
input();
solve();
}
} J Query on A Tree
[题目链接](http://acm.hdu.edu.cn/showproblem.php?pid=6191) 题意：q次查询，给出一棵树，求结点u子树下值与x最大异或值 思路：通过DFS序建立可持久化字典树，在可持久化字典树中查询#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
int n,q;
int v[maxn];
vector <int>G[maxn];
int rt[maxn];
struct Persistent_Trie {
int tot;
int ch[maxn * 32][2];//开logn+2倍
int sum[maxn * 32];
void init() {
tot = 0;
memset(ch, 0, sizeof(ch));
memset(sum, 0, sizeof(sum));
}
void insert(int &x, int y, int val) {
int sta;
int t;
x = sta = ++tot;
for (int i = 30; i >= 0; i--) {
ch[sta][0] = ch[y][0];
ch[sta][1] = ch[y][1];
sum[sta] = sum[y] + 1;
t = val & (1 << i); t >>= i;
y = ch[y][t];
ch[sta][t] = ++tot;
sta = ch[sta][t];
}
sum[sta] = sum[y] + 1;
}
int query(int x, int y, int val) {
int res = 0;
for (int i = 30; i >= 0; i--) {
int t = val & (1 << i); t >>= i;
if (sum[ch[y][t ^ 1]] - sum[ch[x][t ^ 1]]) {
res += 1 << i;
y = ch[y][t ^ 1];
x = ch[x][t ^ 1];
}
else {
y = ch[y][t];
x = ch[x][t];
}
}
return res;
}
}pt;
int dfs_num[maxn];
int L[maxn],R[maxn];
int cnt;
void dfs(int x,int fa){
L[x]=++cnt;
dfs_num[cnt]=x;
for(int i=0;i<G[x].size();i++){
if(G[x][i]==fa)continue;
dfs(G[x][i],x);
}
R[x]=cnt;
}
void input(){
pt.init();
cnt=0;
int i,u,x;
for(i=1;i<=n;i++){
scanf("%d",&v[i]);
G[i].clear();
}
for(i=2;i<=n;i++){
scanf("%d",&x);
G[x].push_back(i);
}
dfs(1,-1);
for(i=1;i<=cnt;i++){
pt.insert(rt[i],rt[i-1],v[dfs_num[i]]);
}
for(i=1;i<=q;i++){
scanf("%d%d",&u,&x);
printf("%d\n",pt.query(rt[L[u]-1],rt[R[u]],x));
}
}
//void solve(){
//
//}
int main(){
while(scanf("%d%d",&n,&q)!=EOF){
input();
// solve();
}
}
京公网安备 11010502036488号