华华听月月唱歌

贪心

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define eb emplace_back
 8 #define maxn 100005
 9 #define eps 1e-8
10 #define pi acos(-1.0)
11 #define rep(k,i,j) for(int k=i;k<j;k++)
12 typedef long long ll;
13 typedef pair<int,int> pii;
14 typedef pair<char,int> pci;
15 typedef pair<pair<int,string>,pii> ppp;
16 typedef unsigned long long ull;
17 const long long MOD=1e9+9;
18 /*#ifndef ONLINE_JUDGE
19         freopen("1.txt","r",stdin);
20 #endif */
21 
22 int n,m;
23 vector<pii>ve;
24 
25 bool cmp(pii a,pii b){
26     if(a.first==b.first) return a.second>b.second;
27     return a.first<b.first;
28 }
29 
30 int main(){
31     #ifndef ONLINE_JUDGE
32      //   freopen("1.txt","r",stdin);
33     #endif
34     std::ios::sync_with_stdio(false);
35     cin>>n>>m;
36     int u,v;
37     for(int i=1;i<=m;i++){
38         cin>>u>>v;
39         ve.pb(make_pair(u,v));
40     }
41     sort(ve.begin(),ve.end(),cmp);
42     int ans=1;
43     int last=ve[0].second;
44     int tmp=ve[0].second;
45     for(int i=1;i<ve.size();i++){
46         if(ve[i].first<=last) {
47             tmp=max(ve[i].second,tmp);
48         }
49         else{
50             if(ve[i].first-last<=1){
51                 last=ve[i].second;
52                 tmp=last;
53                 ans++;
54             }
55             else if(ve[i].first-tmp<=1){
56                 ans+=1;
57                 last=tmp;
58                 i--;
59             }
60             else{
61                 cout<<-1<<endl;
62                 return 0;
63             }
64         }
65     }
66     if(last!=n&&tmp==n) ans++;
67     cout<<ans<<endl;
68 }

View Code

华华教月月做数学

快速幂

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define eb emplace_back
 8 #define maxn 100005
 9 #define eps 1e-8
10 #define pi acos(-1.0)
11 #define rep(k,i,j) for(int k=i;k<j;k++)
12 typedef long long ll;
13 typedef pair<int,int> pii;
14 typedef pair<char,int> pci;
15 typedef pair<pair<int,string>,pii> ppp;
16 typedef unsigned long long ull;
17 const long long MOD=1e9+9;
18 /*#ifndef ONLINE_JUDGE
19         freopen("1.txt","r",stdin);
20 #endif */
21 
22 ll p;
23 ll pow_mul(ll aa,ll b){
24     __int128 ans=1,a=aa%p;
25     while(b){
26         if(b&1){
27             ans=((ans%p)*(a%p))%p;
28         }
29         a=((a%p)*(a%p))%p;
30         b>>=1;
31     }
32     return ans;
33 }
34 
35 int main(){
36     #ifndef ONLINE_JUDGE
37      //   freopen("1.txt","r",stdin);
38     #endif
39     std::ios::sync_with_stdio(false);
40     int t;
41     cin>>t;
42     ll a,b;
43     while(t--){
44         cin>>a>>b>>p;
45         cout<<pow_mul(a,b)<<endl;
46     }
47 }

View Code

华华给月月出题

因为合数a可以由两个比它小的数相乘得到。所以用线性筛求出素数和合数，素数的d[i]的值只能用快速幂求出，合数可以用之前求过的两个数相乘直接得到

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define eb emplace_back
 8 #define maxn 13000005
 9 #define eps 1e-8
10 #define pi acos(-1.0)
11 #define rep(k,i,j) for(int k=i;k<j;k++)
12 typedef long long ll;
13 typedef pair<int,int> pii;
14 typedef pair<char,int> pci;
15 typedef pair<pair<int,string>,pii> ppp;
16 typedef unsigned long long ull;
17 const long long MOD=1e9+7;
18 /*#ifndef ONLINE_JUDGE
19         freopen("1.txt","r",stdin);
20 #endif */
21 
22 ll prime[maxn];
23 bool isprime[maxn];
24 ll d[maxn];
25 int tot;
26 
27 ll pow_mul(ll a,ll b){
28     ll ans=1;
29     while(b){
30         if(b&1){
31             ans=ans*a%MOD;
32         }
33         a=a*a%MOD;
34         b>>=1;
35     }
36     return ans;
37 }
38 
39 void init(int n){
40     memset(isprime,true,sizeof(isprime));
41     for(int i=2;i<=n;i++){
42         if(isprime[i]){
43             prime[++tot]=i;
44             d[i]=pow_mul(i,n);
45         }
46         for(int j=1;j<=tot&&i*prime[j]<=n;j++){
47             isprime[i*prime[j]]=false;
48             d[i*prime[j]]=1ll*d[i]*d[prime[j]]%MOD;
49             if(i%prime[j]==0) break;
50         }
51     }
52 }
53 
54 
55 int main(){
56     #ifndef ONLINE_JUDGE
57      //   freopen("1.txt","r",stdin);
58     #endif
59     std::ios::sync_with_stdio(false);
60     int n;
61     cin>>n;
62     init(n);
63     ll ans=1;
64     for(int i=1;i<=n;i++){
65         ans^=d[i];
66     }
67     cout<<ans<<endl;
68 }

View Code

月月给华华出题

数学渣。。感觉这题是这套题中最难的= =，根据下图的式子，可以看出答案和欧拉函数有关，所以直接用线性筛求欧拉函数

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define eb emplace_back
 8 #define maxn 1000006
 9 #define eps 1e-8
10 #define pi acos(-1.0)
11 #define rep(k,i,j) for(int k=i;k<j;k++)
12 typedef long long ll;
13 typedef pair<int,int> pii;
14 typedef pair<char,int> pci;
15 typedef pair<pair<int,string>,pii> ppp;
16 typedef unsigned long long ull;
17 const long long MOD=1e9+7;
18 /*#ifndef ONLINE_JUDGE
19         freopen("1.txt","r",stdin);
20 #endif */
21 
22 int prime[maxn];
23 int vis[maxn];
24 int tot;
25 ll phi[maxn],ans[maxn];
26 
27 void Init(int n){
28     phi[1]=1;
29     for(int i=2;i<=n;i++){
30         if(!vis[i]){
31             prime[++tot]=i;
32             phi[i]=i-1;
33         }
34         for(int j=1;j<=tot&&i*prime[j]<=n;j++){
35             vis[i*prime[j]]=true;
36             if(i%prime[j]==0){
37                 phi[i*prime[j]]=phi[i]*prime[j];
38                 break;
39             }
40             phi[i*prime[j]]=phi[i]*(prime[j]-1);
41         }
42     }
43 }
44 
45 int main(){
46     #ifndef ONLINE_JUDGE
47        // freopen("1.txt","r",stdin);
48     #endif
49     std::ios::sync_with_stdio(false);
50     int n;
51     scanf("%d",&n);
52     Init(n);
53     for(int i=2;i<=n;i++) phi[i]=phi[i]*i/2;
54     for(int i=1;i<=n;i++){
55         for(int j=i;j<=n;j+=i){
56             ans[j]+=phi[i];
57         }
58     }
59     for(int i=1;i<=n;i++) printf("%lld
",ans[i]);
60 }

View Code

华华给月月准备礼物

二分

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define eb emplace_back
 8 #define maxn 100005
 9 #define eps 1e-8
10 #define pi acos(-1.0)
11 #define rep(k,i,j) for(int k=i;k<j;k++)
12 typedef long long ll;
13 typedef pair<int,int> pii;
14 typedef pair<char,int> pci;
15 typedef pair<pair<int,string>,pii> ppp;
16 typedef unsigned long long ull;
17 const long long MOD=1e9+9;
18 /*#ifndef ONLINE_JUDGE
19         freopen("1.txt","r",stdin);
20 #endif */
21 
22 ll n,k;
23 int a[200005];
24 
25 bool erfen(ll mid){
26     ll sum=0;
27     for(int i=1;i<=n;i++){
28         sum+=a[i]/mid;
29     }
30     if(sum>=k) return true;
31     return false;
32 }
33 
34 int main(){
35     #ifndef ONLINE_JUDGE
36      //   freopen("1.txt","r",stdin);
37     #endif
38     std::ios::sync_with_stdio(false);
39     cin>>n>>k;
40     ll sum=0;
41     for(int i=1;i<=n;i++){
42         cin>>a[i];
43         sum+=a[i];
44     }
45     ll L=1,R=1e9,mid;
46     while(L<=R){
47         mid=L+R>>1;
48         if(erfen(mid)){
49             L=mid+1;
50         }
51         else{
52             R=mid-1;
53         }
54     }
55     cout<<R<<endl;
56 }

View Code

华华开始学信息学

分块+树状数组

当d<=sqrt(n)时，如果要更新的话，代价有点大，所以用一个数组保存当d<=sqrt(n)时的更新。当D>sqrt(n)时，暴力更新，因为复杂度不会超过sqrt(n)

然后求和的时候把d<=sqrt(n)的值更新一下就行

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define eb emplace_back
 8 #define maxn 200005
 9 #define eps 1e-8
10 #define pi acos(-1.0)
11 #define rep(k,i,j) for(int k=i;k<j;k++)
12 typedef long long ll;
13 typedef pair<int,int> pii;
14 typedef pair<char,int> pci;
15 typedef pair<pair<int,string>,pii> ppp;
16 typedef unsigned long long ull;
17 const long long MOD=1e9+7;
18 /*#ifndef ONLINE_JUDGE
19         freopen("1.txt","r",stdin);
20 #endif */
21 
22 ll a[100005];
23 ll book[1005];
24 int n;
25 
26 int lowbit(int x){return x&(-x);}
27 
28 ll getsum(int x){
29     ll sum=0;
30     while(x){
31         sum+=a[x];
32         x-=lowbit(x);
33     }
34     return sum;
35 }
36 
37 void add(int x,int k){
38     while(x<=n){
39         a[x]+=k;
40         x+=lowbit(x);
41     }
42 }
43 
44 int main(){
45     #ifndef ONLINE_JUDGE
46        // freopen("1.txt","r",stdin);
47     #endif
48     std::ios::sync_with_stdio(false);
49     int m;
50     cin>>n>>m;
51     int pos,x,y;
52     int sq=sqrt(n);
53     for(int i=1;i<=m;i++){
54         cin>>pos>>x>>y;
55         if(pos==1){
56             if(x<=sq){
57                 book[x]+=y;
58             }
59             else{
60                 for(int j=x;j<=n;j+=x){
61                     add(j,y);
62                 }
63             }
64         }
65         else{
66             ll ans=getsum(y)-getsum(x-1);
67             for(int j=1;j<=sq;j++){
68                 ans+=book[j]*(y/j-(x-1)/j);
69             }
70             cout<<ans<<endl;
71         }
72     }
73 
74 }

View Code

华华对月月的忠诚

因为gcd(a,b)==gcd(b,a%b)==gcd(b,a-b)...所以是结论题

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define eb emplace_back
 8 #define maxn 100005
 9 #define eps 1e-8
10 #define pi acos(-1.0)
11 #define rep(k,i,j) for(int k=i;k<j;k++)
12 typedef long long ll;
13 typedef pair<int,int> pii;
14 typedef pair<char,int> pci;
15 typedef pair<pair<int,string>,pii> ppp;
16 typedef unsigned long long ull;
17 const long long MOD=1e9+9;
18 /*#ifndef ONLINE_JUDGE
19         freopen("1.txt","r",stdin);
20 #endif */
21 
22 
23 
24 int main(){
25     #ifndef ONLINE_JUDGE
26      //   freopen("1.txt","r",stdin);
27     #endif
28     std::ios::sync_with_stdio(false);
29     ll a,b,c;
30     cin>>a>>b>>c;
31     cout<<__gcd(a,b)<<endl;
32 }

View Code

华华和月月种树

先离线，然后跑树剖就好（感觉这做法有点麻烦,用树状数组好像也可以做），注意，当新加入一个节点时，他可能已经有值了，所以在新增一个节点时，需要清空他和他子孙的值

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define lson l,mid,rt<<1
  4 #define rson mid+1,r,rt<<1|1
  5 #define sqr(x) ((x)*(x))
  6 #define pb push_back
  7 #define eb emplace_back
  8 #define maxn 200005
  9 #define eps 1e-8
 10 #define pi acos(-1.0)
 11 #define rep(k,i,j) for(int k=i;k<j;k++)
 12 typedef long long ll;
 13 typedef pair<int,int> pii;
 14 typedef pair<char,int> pci;
 15 typedef pair<pair<int,string>,pii> ppp;
 16 typedef unsigned long long ull;
 17 const long long MOD=1e9+7;
 18 /*#ifndef ONLINE_JUDGE
 19         freopen("1.txt","r",stdin);
 20 #endif */
 21 
 22 int tree[maxn<<3],lazy[maxn<<3],zero[maxn<<3];
 23 int n;
 24 int dep[maxn],fa[maxn],siz[maxn],son[maxn],id[maxn],top[maxn],cnt;
 25 vector<int>ve[maxn];
 26 int tot=1;
 27 
 28 void pushup(int rt){
 29     tree[rt]=max(tree[rt<<1],tree[rt<<1|1]);
 30 }
 31 
 32 void pushdown(int rt){
 33     if(zero[rt]){
 34         zero[rt<<1]=1;
 35         zero[rt<<1|1]=1;
 36         tree[rt<<1]=0;
 37         tree[rt<<1|1]=0;
 38         lazy[rt<<1]=0;
 39         lazy[rt<<1|1]=0;
 40         zero[rt]=0;
 41     }
 42     if(lazy[rt]){
 43         lazy[rt<<1]+=lazy[rt];
 44         lazy[rt<<1|1]+=lazy[rt];
 45         tree[rt<<1]+=lazy[rt];
 46         tree[rt<<1|1]+=lazy[rt];
 47         lazy[rt]=0;
 48     }
 49 }
 50 
 51 void build(int l,int r,int rt){
 52     lazy[rt]=0;
 53     if(l==r){
 54         tree[rt]=0;
 55         return;
 56     }
 57     int mid=(l+r)/2;
 58     build(lson);
 59     build(rson);
 60     pushup(rt);
 61 }
 62 
 63 void init(int L,int R,int l,int r,int rt){
 64     if(L<=l&&R>=r){
 65         tree[rt]=0;
 66         lazy[rt]=0;
 67         zero[rt]=1;
 68         pushdown(rt);
 69         return;
 70     }
 71     int mid=l+r>>1;
 72     pushdown(rt);
 73     if(L<=mid) init(L,R,lson);
 74     if(R>mid) init(L,R,rson);
 75     pushup(rt);
 76 }
 77 
 78 void add(int L,int R,int k,int l,int r,int rt){
 79     if(L<=l&&R>=r){
 80         pushdown(rt);
 81         tree[rt]+=k;
 82         lazy[rt]+=k;
 83         return;
 84     }
 85     int mid=(l+r)/2;
 86     pushdown(rt);
 87     if(L<=mid) add(L,R,k,lson);
 88     if(R>mid) add(L,R,k,rson);
 89     pushup(rt);
 90 }
 91 
 92 int query(int L,int l,int r,int rt){
 93     if(l==r){
 94         pushdown(rt);
 95         return tree[rt];
 96     }
 97     int mid=(l+r)/2;
 98     pushdown(rt);
 99     int ans=0;
100     if(L<=mid) return query(L,lson);
101     else return query(L,rson);
102     pushup(rt);
103     return ans;
104 }
105 
106 void dfs1(int now,int f,int deep){
107     dep[now]=deep;
108     siz[now]=1;
109     fa[now]=f;
110     int maxson=-1;
111     for(int i=0;i<ve[now].size();i++){
112         if(ve[now][i]==f) continue;
113         dfs1(ve[now][i],now,deep+1);
114         siz[now]+=siz[ve[now][i]];
115         if(siz[ve[now][i]]>maxson){
116             maxson=siz[ve[now][i]];
117             son[now]=ve[now][i];
118         }
119     }
120 }
121 
122 void dfs2(int now,int topp){
123     id[now]=++cnt;
124     top[now]=topp;
125     if(!son[now]) return;
126     dfs2(son[now],topp);
127     for(int i=0;i<ve[now].size();i++){
128         if(ve[now][i]==son[now]||ve[now][i]==fa[now]) continue;
129         dfs2(ve[now][i],ve[now][i]);
130     }
131 }
132 
133 
134 void addSon(int x,int k){
135     add(id[x],id[x]+siz[x]-1,k,1,tot,1);
136 }
137 
138 void addSon(int x){
139     init(id[x],id[x]+siz[x]-1,1,tot,1);
140 }
141 
142 struct sair{
143     int pos,x,y;
144 }a[maxn<<1];
145 
146 int main(){
147     #ifndef ONLINE_JUDGE
148        // freopen("1.txt","r",stdin);
149     #endif
150     std::ios::sync_with_stdio(false);
151     cin>>n;
152     int pos;
153     for(int i=1;i<=n;i++){
154         cin>>a[i].pos>>a[i].x;
155         a[i].x++;
156         if(a[i].pos==2){
157             cin>>a[i].y;
158         }
159         if(a[i].pos==1){
160             ++tot;
161             ve[a[i].x].pb(tot);
162             ve[tot].pb(a[i].x);
163         }
164     }
165     cnt=0;
166     dfs1(1,0,1);
167     dfs2(1,1);
168     build(1,tot,1);
169     int co=2;
170     for(int i=1;i<=n;i++){
171         if(a[i].pos==1){
172             addSon(co);
173             co++;
174         }
175         else if(a[i].pos==2){
176             addSon(a[i].x,a[i].y);
177         }
178         else if(a[i].pos==3){
179             cout<<query(id[a[i].x],1,tot,1)<<endl;
180         }
181     }
182 
183 }

View Code

华华和月月逛公园

跑tarjan就行

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define eb emplace_back
 8 #define maxn 200005
 9 #define eps 1e-8
10 #define pi acos(-1.0)
11 #define rep(k,i,j) for(int k=i;k<j;k++)
12 typedef long long ll;
13 typedef pair<int,int> pii;
14 typedef pair<char,int> pci;
15 typedef pair<pair<int,string>,pii> ppp;
16 typedef unsigned long long ull;
17 const long long MOD=1e9+9;
18 /*#ifndef ONLINE_JUDGE
19         freopen("1.txt","r",stdin);
20 #endif */
21 
22 vector<int>ve[maxn];
23 int n,m,dfn[maxn],low[maxn],vis[maxn],tot,ans;
24 stack<int>st;
25 
26 void dfs(int u,int pre){
27     low[u]=dfn[u]=++tot;
28     for(int i=0;i<ve[u].size();i++){
29         int v=ve[u][i];
30         if(!dfn[v]){
31             dfs(v,u);
32             low[u]=min(low[v],low[u]);
33             if(low[v]>dfn[u]) ans++;
34         }
35         else if(v!=pre){
36             low[u]=min(low[u],dfn[v]);
37         }
38     }
39 }
40 
41 
42 int main(){
43     #ifndef ONLINE_JUDGE
44      //   freopen("1.txt","r",stdin);
45     #endif
46     std::ios::sync_with_stdio(false);
47     cin>>n>>m;
48     int u,v;
49     for(int i=1;i<=m;i++){
50         cin>>u>>v;
51         ve[u].pb(v);
52         ve[v].pb(u);
53     }
54     dfs(1,0);
55     printf("%d
",m-ans);
56 }

View Code