gym 101915

5/8

昨晚单切打了两个小时被人叫去打游戏了(大雾，带妹(小姐姐)五杀真爽啊。

比赛+补题只写了八个

A：挺可爱的吧，，，我们从低位到高位算 “包含这些数位的数字”有多少个，如果n大于这个，就减去然后算大一位的，如果不大于，看是否能整除，答案就是之前的加上 n除以这个的，如果不能整除就 gg 了。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 ll qpow(ll x,ll n){
 5     ll ans = x;
 6     for(int i=1;i<n;i++){
 7         ans*=x;
 8     }
 9     return ans;
10 }
11 ll t;
12 ll n,x;
13 int main(){
14     ios::sync_with_stdio(false);
15     cin>>t;
16     while (t--){
17         cin>>n>>x;
18         int len = 0;
19         ll xx = x;
20         while (xx){
21             len++;
22             xx/=10;
23         }
24         ll tmp = qpow(10,len);
25         ll n1 = tmp-x;//当前数位的数字个数
26         //cout<<n1;
27         ll ans = 0;
28         //bool flag = true;
29         while(n){
30             if(n>n1*len){
31                 n-=n1*len;
32                 ans+=n1;
33                 len++;
34                 n1 = tmp*10-tmp;
35                 tmp*=10;
36             } else if(n%len){
37                 cout<<-1<<endl;
38                 break;
39             } else{
40                 ans+=n/len;
41                 cout<<ans<<endl;
42                 break;
43             }
44         }
45     }
46 }

View Code

B：这种15个人的题我怎么可能会呢23333(逃

C：签到

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 ll t,k,p,n;
 5 int main(){
 6     ios::sync_with_stdio(false);
 7     cin>>t;
 8     while (t--){
 9         cin>>k>>p>>n;
10         cout<<max(0ll,(k-p)*n)<<endl;
11     }
12 }

View Code

D：最大团吧，，，其实这玩意我也不会，就百度了份板子粘上去过了，不过我发现他讲最大团讲得特别好，附链接

http://www.cnblogs.com/zhj5chengfeng/archive/2013/07/29/3224092.html

打算过几天(下个赛季认真学学

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 
 5 using namespace std;
 6 
 7 struct MAX_CLIQUE {
 8     static const int N=60;
 9 
10     bool G[N][N];
11     int n, Max[N], Alt[N][N], ans;
12 
13     bool DFS(int cur, int tot) {
14         if(cur==0) {
15             if(tot>ans) {
16                 ans=tot;
17                 return 1;
18             }
19             return 0;
20         }
21         for(int i=0; i<cur; i++) {
22             if(cur-i+tot<=ans) return 0;
23             int u=Alt[tot][i];
24             if(Max[u]+tot<=ans) return 0;
25             int nxt=0;
26             for(int j=i+1; j<cur; j++)
27                 if(G[u][Alt[tot][j]]) Alt[tot+1][nxt++]=Alt[tot][j];
28             if(DFS(nxt, tot+1)) return 1;
29         }
30         return 0;
31     }
32 
33     int MaxClique() {
34         ans=0, memset(Max, 0, sizeof Max);
35         for(int i=n-1; i>=0; i--) {
36             int cur=0;
37             for(int j=i+1; j<n; j++) if(G[i][j]) Alt[1][cur++]=j;
38             DFS(cur, 1);
39             Max[i]=ans;
40         }
41         return ans;
42     }
43 };
44 MAX_CLIQUE fuck;
45 int t,n,m,a,b;
46 int main() {
47     cin>>t;
48     while(t--) {
49         cin>>n>>m;
50         memset(fuck.G,0, sizeof(fuck.G));
51         fuck.n = 2*n;
52         while (m--){
53             cin>>a>>b;
54             fuck.G[a-1][b+n-1]=1;
55         }
56         for(int i=0;i<n;i++){
57             for(int j=i+1;j<n;j++){
58                 fuck.G[i][j]=1;
59             }
60         }
61         for(int i=n;i<2*n;i++){
62             for(int j=i+1;j<2*n;j++){
63                 fuck.G[i][j]=1;
64             }
65         }
66         printf("%d
", fuck.MaxClique());
67     }
68     return 0;
69 }

View Code

E：这种17个人的题我怎么可能会呢23333(逃

F：签到

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 int t,n,a;
 5 bool vis[18];
 6 int main(){
 7     ios::sync_with_stdio(false);
 8     cin>>t;
 9     while (t--){
10         memset(vis, false, sizeof(vis));
11         cin>>n;
12         for(int i=1;i<n;i++){
13             cin>>a;
14             vis[a]=true;
15         }
16         for(int i=1;i<=n;i++){
17             if(!vis[i]){
18                 cout<<i<<endl;
19                 break;
20             }
21         }
22     }
23 }

View Code

G:很有意思的一道题，

题意：给你一棵树，每条边有权值。给你q个机器人，每个机器人有一个权值，机器人全部从1节点出发，机器人走的边必须是权值最大的小于机器人权值的边，这样子到最后机器人就会停在某个节点，对所有机器人停留的结点编号求和。

看了别人的才懂的，

首先我们能想到对机器人和每个结点的边按权值排序，因为机器人的顺序是无关紧要的，结点很明显从大到小排，这样可以保证第一个可以走的结点就是最优的。

机器人也要按权值从大到小排序(嗯...这样子然后搜一遍就可以了，感觉很巧妙额，哦对还要预处理出每个点要求的权值。

不行我要回去看IG打KT了，不写多了

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 struct node{
 5     int to,w;
 6     node(int to,int w):to(to),w(w){}
 7 };
 8 bool cmp(node a,node b){
 9     return a.w>b.w;
10 }
11 vector<node>g[100005];
12 int t,n,q,u,v,w,x;
13 int par[100005],maxx[100005];
14 priority_queue<int> que;
15 void predfs(int v,int fa){
16     for(int i=0;i<g[v].size();i++){
17         node tmp = g[v][i];
18         if(tmp.to==fa)
19             continue;
20         int u = tmp.to;
21         par[u]=v;
22         maxx[u]=max(maxx[v],tmp.w);
23         predfs(u,v);
24     }
25 }
26 void dfs(int x,ll &ans){
27     if(que.top()>maxx[x]){
28         for(int i=0;i<g[x].size();i++){
29             node tmp = g[x][i];
30             if(tmp.to==par[x])
31                 continue;
32             if(que.top()>tmp.w){
33                 dfs(tmp.to,ans);
34             }
35         }
36         while (!que.empty()&&que.top()>maxx[x]){
37             ans+=x;
38             que.pop();
39         }
40     }
41 }
42 void init(int n){
43     for(int i=0;i<=n;i++)
44         g[i].clear();
45     memset(par,0, sizeof(par));
46     memset(maxx,0, sizeof(maxx));
47 }
48 int main(){
49     ios::sync_with_stdio(false);
50     cin>>t;
51     while (t--){
52         cin>>n>>q;
53         init(n);
54         for(int i=1;i<n;i++){
55             cin>>u>>v>>w;
56             g[u].push_back(node(v,w));
57             g[v].push_back(node(u,w));
58         }
59         while (q--){
60             cin>>x;
61             que.push(x);
62         }
63         for(int i=1;i<=n;i++){
64             sort(g[i].begin(),g[i].end(),cmp);
65         }
66         predfs(1,0);
67         ll ans = 0;
68         dfs(1,ans);
69         cout<<ans<<endl;
70     }
71 }

View Code

H：签到

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 int t,n,k;
 5 int a[5];
 6 vector<int> v;
 7 int main(){
 8     ios::sync_with_stdio(false);
 9     cin>>t;
10     while (t--){
11         v.clear();
12         cin>>n>>k;
13         for(int i=1;i<=n;i++){
14             cin>>a[1]>>a[2]>>a[3];
15             sort(a+1,a+4);
16             v.push_back(a[1]);
17             v.push_back(a[2]);
18         }
19         sort(v.begin(),v.end());
20         int ans = 0;
21         for(int i=0;i<k;i++){
22             ans+=v[i];
23         }
24         cout<<ans<<endl;
25     }
26 }

View Code

J：简单几何，并查集就完了，也不用考虑精度

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 //const double eps = 1e-6;
 5 int fa[1005],ran[1005];
 6 int find(int a){
 7     if(a==fa[a])
 8         return a;
 9     else
10         return fa[a]=find(fa[a]);
11 }
12 void unite(int x,int y){
13     x = find(x);
14     y = find(y);
15     if (x==y) return;
16     if(ran[x]<ran[y]) fa[x] = y;
17     else{
18         fa[y] = x;
19         if(ran[x] ==ran[y])
20             ran[x]++;
21     }
22 }
23 bool same(int x,int y){
24     return find(x)==find(y);
25 }
26 int t;
27 ll n,w,l;
28 ll x[1005],y[1005],r[1005];
29 ll sqr(ll x){return x*x;}
30 bool check(int a,int b){//是否相交
31     return (sqr(x[a]-x[b])+sqr(y[a]-y[b]))<=sqr(r[a]+r[b]);
32 }
33 map<int,int> m;
34 vector<int> v[1006];
35 int main(){
36     ios::sync_with_stdio(false);
37     cin>>t;
38     while (t--){
39         m.clear();
40         for(int i=1;i<=1000;i++)
41             v[i].clear();
42         cin>>n>>w>>l;
43         for(int i=1;i<=n;i++){
44             cin>>x[i]>>y[i]>>r[i];
45         }
46         for(int i=1;i<=n;i++){
47             fa[i]=i;
48             ran[i]=0;
49         }
50         for(int i=1;i<=n;i++){
51             for(int j=i+1;j<=n;j++){
52                 if(check(i,j))
53                     unite(i,j);
54             }
55         }
56         int cnt = 1;
57         for(int i=1;i<=n;i++){
58             int f = find(i);
59             if(m[f]){
60                 v[m[f]].push_back(i);
61             } else{
62                 m[f]=cnt++;
63                 v[m[f]].push_back(i);
64             }
65         }
66         int ans = 0;
67         for(int i=1;i<cnt;i++){
68             ll lef = 1e9;
69             ll rig = 0;
70             for(int j=0;j<v[i].size();j++){
71                 int cur = v[i][j];
72                 rig = max(rig,r[cur]+x[cur]);
73                 lef = min(lef,x[cur]-r[cur]);
74             }
75             if(lef<=0&&rig>=w){
76                 ans++;
77             }
78         }
79         cout<<ans<<endl;
80     }
81 }

View Code

K：搜索题，我不会搜索。。。搜的题解

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const ll mod = 1e9+7;
 5 ll t,len;
 6 ll dp[60][60];
 7 char s[60];
 8 ll dfs(int l,int r){
 9     if(l>=r)
10         return 1;
11     if(dp[l][r]!=-1)
12         return dp[l][r];
13     ll ret = 0;
14     int lsum = 0;
15     for(int i=l;i<len;i++){
16         lsum+=s[i]-'0';
17         int rsum = 0;
18         for(int j=r;j>i;j--){
19             rsum+=s[j]-'0';
20             if(rsum==lsum)
21                 ret+=dfs(i+1,j-1);
22             else if(rsum>lsum)
23                 break;
24         }
25     }
26     ret++;//中间全放上(
27     ret%=mod;
28     dp[l][r]=ret;
29     return ret;
30 }
31 int main(){
32     ios::sync_with_stdio(false);
33     cin>>t;
34     while (t--){
35         memset(dp,-1, sizeof(dp));
36         cin>>s;
37         len = strlen(s);
38         cout<<dfs(0,len-1)<<endl;
39     }
40 }

View Code