国庆训练 10.3

过了好几天了，还有好多题要补，先更个博客，万一过几天就忘光了。。。

先把格子填满，记录填充数目，然后倒着做，当某个格子变为0的时候，就和四周能合并的格子合并。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int n,m,q;
 5 struct node{
 6     int x1,y1,xx,yy;
 7 } que[10005];
 8 int num[1000005];
 9 int f[1000005];
10 int find(int x){
11     return f[x]==x?x:f[x]=find(f[x]);
12 }
13 int cnt;
14 void merge(int x,int y){
15     //cout<<x<<" "<<y<<endl;
16     int fx=find(x);
17     int fy=find(y);
18     if(fx==fy) return;
19     //cout<<fx<<" "<<fy<<endl;
20     //system("pause");
21     cnt--; f[fx]=fy;
22 }
23 int getid(int x,int y){
24     return x*m+y;
25 }
26 int ans[10005];
27 int fx[]={0,0,1,-1};
28 int fy[]={1,-1,0,0};
29 bool in(int x,int y){
30     return x>=0&&y>=0&&x<n&&y<m;
31 }
32 void solve(int x,int y){
33     for(int k=0;k<4;k++){
34         int tx=x+fx[k];
35         int ty=y+fy[k];
36         if(!in(tx,ty)||num[getid(tx,ty)]) continue;
37         merge(getid(tx,ty),getid(x,y));
38     }
39 }
40 int main(){
41     scanf("%d%d%d",&m,&n,&q);
42     cnt=n*m;
43     for(int i=0;i<n*m;i++) f[i]=i,num[i]=0;
44     for(int i=0;i<q;i++){
45         scanf("%d%d%d%d",&que[i].y1,&que[i].x1,&que[i].yy,&que[i].xx);
46         que[i].x1--; que[i].y1--;
47         que[i].xx--; que[i].yy--;
48         for(int x=que[i].x1;x<=que[i].xx;x++)
49         for(int y=que[i].y1;y<=que[i].yy;y++){
50             if(num[getid(x,y)]==0) cnt--;
51             num[getid(x,y)]++;
52         }
53     }
54     for(int i=0;i<n;i++){
55         for(int j=0;j<m;j++){
56             if(num[getid(i,j)]) continue;
57             solve(i,j);
58         }
59     }
60     for(int i=q-1;i>=0;i--){
61         ans[i]=cnt;
62         for(int x=que[i].x1;x<=que[i].xx;x++)
63         for(int y=que[i].y1;y<=que[i].yy;y++){
64             num[getid(x,y)]--;
65             if(num[getid(x,y)]==0) {
66                 cnt++;
67                 solve(x,y);
68                 //cout<<x<<" "<<y<<" "<<cnt<<endl;
69             }
70         }
71     }
72 
73     for(int i=0;i<q;i++){
74         printf("%d
",ans[i]);
75     }
76 
77     return 0;
78 }

Psong

Kattis autocorrect

把单词放入字典树，把单词末尾打上标记，每个节点再向自己子树里面最早添加的并且带标记的节点连边，然后bfs，每个节点的后继按照所给单词重新定序。

Kattis cardhand

暴力所有顺序的情况，对于每种情况最长上升子序列即可。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int n;
 5 char s[5];
 6 int a[55],b[55];
 7 
 8 int cnt;
 9 int shunxu[55];
10 int huase[55];
11 int vis[55];
12 map<pair<int,int>,int >mp;
13 
14 int xulie[55];
15 
16 int ans;
17 int dp[55];
18 void solve(){
19     for(int i=1;i<=n;i++){
20         dp[i]=1;
21         for(int j=1;j<i;j++){
22             if(xulie[j]<=xulie[i]){
23                 dp[i]=max(dp[i],dp[j]+1);
24             }
25         }
26         ans=max(ans,dp[i]);
27     }
28 }
29 
30 void build(){
31     int tot=0;
32     for(int i=1;i<=4;i++){
33         if(shunxu[i]==0)
34             for(int j=1;j<=13;j++){
35                 mp[make_pair(j,huase[i])]=++tot;
36             }
37         else
38             for(int j=13;j>=1;j--){
39                 mp[make_pair(j,huase[i])]=++tot;
40             }
41     }
42     for(int i=1;i<=n;i++){
43         xulie[i]=mp[make_pair(a[i],b[i])];
44     }
45     solve();
46 }
47 
48 void dfs2(int now){
49     if(now>4){
50         build();
51         return;
52     }
53     shunxu[now]=1; dfs2(now+1);
54     shunxu[now]=0; dfs2(now+1);
55 }
56 
57 void dfs(int now){
58     if(now>4){
59         dfs2(1);
60         return;
61     }
62     for(int i=1;i<=4;i++){
63         if(!vis[i]){
64             vis[i]=1;
65             huase[now]=i;
66             dfs(now+1);
67             vis[i]=0;
68         }
69     }
70 }
71 
72 int main(){
73     scanf("%d",&n);
74     for(int i=1;i<=n;i++){
75         scanf("%s",s);
76         if(s[0]=='T') a[i]=9;
77         else if(s[0]=='J') a[i]=10;
78         else if(s[0]=='Q') a[i]=11;
79         else if(s[0]=='K') a[i]=12;
80         else if(s[0]=='A') a[i]=13;
81         else a[i]=s[0]-'0'-1;
82 
83         if(s[1]=='s') b[i]=1;
84         else if(s[1]=='h') b[i]=2;
85         else if(s[1]=='d') b[i]=3;
86         else if(s[1]=='c') b[i]=4;
87     }
88     ans=0; dfs(1);
89     printf("%d
",n-ans);
90 
91     return 0;
92 }
93 /*
94 15
95 2h Th 8c Qh 9d As 2s Qd 2c Jd 8h 2h 3h 9c 8c
96 */

Psong

Kattis stockbroker

贪心，当有第i+1天比第i天贵，就再第i天买入，i+1天卖出。

Kattis exponial

欧拉降幂公式，很快幂数就会变为1，并不会再改变。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long LL;
 5 
 6 LL m;
 7 
 8 LL euler(LL n){
 9     LL ans=n;
10     for(LL i=2;i*i<=n;i++){
11         if(n%i==0){
12             ans-=ans/i;
13             while(n%i==0) n/=i;
14         }
15     }
16     if(n>1) ans-=ans/n;
17     return ans;
18 }
19 
20 LL pow_mod(LL a,LL n,LL mod){
21     LL res=1,t=a;
22     while(n){
23         if(n&1) res=(res*t)%mod;
24         t=(t*t)%mod;
25         n/=2;
26     }
27     return res;
28 }
29 
30 LL n;
31 
32 LL dfs(LL x,LL mod){
33     if(x==5) return pow_mod(5,262144,mod);
34     if(x==4) return 262144;
35     if(x==3) return 9;
36     if(x==2) return 2;
37     if(x==1) return 1;
38     if(mod==1) return 0;
39     return pow_mod(x,dfs(x-1,euler(mod))+euler(mod),mod);
40 }
41 
42 int main(){
43     scanf("%lld%lld",&n,&m);
44     printf("%lld
",dfs(n,m)%m);
45 
46     return 0;
47 }

Psong

Kattis raffle

不会这个题。

Kattis gamerank

这个也不会。

Kattis tower

把矩形的边长当作顶点，矩形本身当作边，图中每个顶点最多只有一个出度。

因为所有的矩形都可以被使用，所以每个连通块最多只有一个环。

1.带环的连通块（基环树）：每个点都会有一个出度。

2.不带环的连通块：只有一个点没有出度，取权值最大的点作为没有出度的点。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long LL;
 5 const int MAXN=5e5+5;
 6 
 7 int f[MAXN];
 8 int num_v[MAXN];
 9 int num_e[MAXN];
10 void pre(int n){
11     for(int i=1;i<=n;i++){
12         f[i]=i;
13         num_v[i]=1;
14         num_e[i]=0;
15     }
16 }
17 int find(int x){
18     return f[x]==x?x:f[x]=find(f[x]);
19 }
20 void merge(int x,int y){
21     int fx=find(x),fy=find(y);
22     if(fx==fy){
23         num_e[fx]++;
24         return;
25     }
26     if(fx>fy) swap(fx,fy);
27     num_v[fy]+=num_v[fx];
28     num_e[fy]+=num_e[fx]+1;
29     f[fx]=fy;
30 }
31 
32 vector<int> v;
33 int getid(int x){
34     return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
35 }
36 
37 int n;
38 int vis[MAXN];
39 int s[MAXN],t[MAXN];
40 vector<int> g[MAXN];
41 void addedge(int u,int v){
42     g[u].push_back(v);
43     g[v].push_back(u);
44 }
45 
46 LL ans;
47 void dfs1(int u){
48     vis[u]=1;
49     ans+=v[u-1]*(g[u].size()-1);
50     for(int i=0;i<g[u].size();i++){
51         int Next=g[u][i];
52         if(vis[Next]) continue;
53         dfs1(Next);
54     }
55 }
56 void dfs2(int u){
57     vis[u]=1;
58     for(int i=0;i<g[u].size();i++){
59         int Next=g[u][i];
60         if(vis[Next]) continue;
61         ans+=v[u-1];
62         dfs2(Next);
63     }
64 }
65 
66 int main(){
67     scanf("%d",&n);
68     for(int i=1;i<=n;i++){
69         scanf("%d%d",&s[i],&t[i]);
70         v.push_back(s[i]);
71         v.push_back(t[i]);
72     }
73     sort(v.begin(),v.end());
74     v.erase(unique(v.begin(),v.end()),v.end());
75     pre(v.size());
76     for(int i=1;i<=n;i++){
77         s[i]=getid(s[i]);
78         t[i]=getid(t[i]);
79         addedge(s[i],t[i]);
80         merge(s[i],t[i]);
81     }
82 
83     ans=0;
84     for(int i=1;i<=v.size();i++){
85         int fx=find(i);
86         if(!vis[fx]){
87             if(num_v[fx]==num_e[fx]) dfs1(fx);
88             else dfs2(fx);
89         }
90     }
91     printf("%lld
",ans);
92 
93     return 0;
94 }

Psong

Kattis interception

unsolved

Kattis compass

直接判断两指针位置然后计算答案。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int main(){
 5     int a,b;
 6     int x1,x2;
 7     scanf("%d%d",&a,&b);
 8     if(abs(a-b)==180){
 9         printf("180
");
10         return 0;
11     }
12     else if(a==b){
13         printf("0
");
14         return 0;
15     }
16     else if(a>b){
17         x1=360-a+b;
18         x2=b-a;
19     }
20     else if(a<b){
21         x1=b-a;
22         x2=-(360-b+a);
23     }
24     if(abs(x1)>abs(x2)) printf("%d
",x2);
25     else printf("%d
",x1);
26 
27     return 0;
28 }

Psong

Kattis dogs

分段，然后固定其中一个点，相当于求点到线段最短距离。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int MAXN=1e5+5;
 5 const double eps=1e-8;
 6 
 7 int n,m;
 8 struct Point{
 9     double x,y;
10     Point operator +(const Point &b)const{
11         return (Point){x+b.x,y+b.y};
12     }
13     Point operator -(const Point &b)const{
14         return (Point){x-b.x,y-b.y};
15     }
16     double operator ^(const Point &b)const{
17         return x*b.y-y*b.x;
18     }
19     double operator *(const Point &b)const{
20         return x*b.x+y*b.y;
21     }
22 } a[MAXN],b[MAXN];
23 typedef Point Vector;
24 double abs(Point d){
25     return sqrt(d.x*d.x+d.y*d.y);
26 }
27 Point unit(Point d){
28     return (Point){d.x/abs(d),d.y/abs(d)};
29 }
30 Point mul(double k,Point d){
31     return (Point){d.x*k,d.y*k};
32 }
33 
34 struct Line{
35     Point s,e;
36 };
37 
38 double dis(Point P,Line L){
39     Point res;
40     double t=((P-L.s)*(L.e-L.s))/((L.e-L.s)*(L.e-L.s));
41     if(t>=0&&t<=1){
42         res.x=L.s.x+(L.e.x-L.s.x)*t;
43         res.y=L.s.y+(L.e.y-L.s.y)*t;
44     }
45     else{
46         if(abs(P-L.s)<abs(P-L.e))
47             res=L.s;
48         else res=L.e;
49     }
50     return abs(P-res);
51 }
52 
53 void input(){
54     scanf("%d",&n);
55     for(int i=1;i<=n;i++)
56         scanf("%lf%lf",&a[i].x,&a[i].y);
57     scanf("%d",&m);
58     for(int i=1;i<=m;i++)
59         scanf("%lf%lf",&b[i].x,&b[i].y);
60 }
61 
62 void solve(){
63     double res=1e15;
64     int R1=2,R2=2;
65     Point a_now=a[1],b_now=b[1];
66     while(R1<=n&&R2<=m){
67         Point a_to=a[R1],b_to=b[R2];
68         Vector dir1=unit(a_to-a_now);
69         Vector dir2=unit(b_to-b_now);
70         if(abs(a_to-a_now)>abs(b_to-b_now)){
71             double t=abs(b_to-b_now);
72             Vector delta=dir2-dir1;
73             Point st=b_now;
74             Point ed=b_now+mul(t,delta);
75             res=min(res,dis(a_now,(Line){st,ed}));
76             a_now=a_now+mul(t,dir1);
77             b_now=b[R2]; R2++;
78         }
79         else{
80             double t=abs(a_to-a_now);
81             Vector delta=dir1-dir2;
82             Point st=a_now;
83             Point ed=a_now+mul(t,delta);
84             res=min(res,dis(b_now,(Line){st,ed}));
85             b_now=b_now+mul(t,dir2);
86             a_now=a[R1]; R1++;
87         }
88     }
89     printf("%.12lf
",res);
90 }
91 
92 int main(){
93     input();
94     solve();
95 
96     return 0;
97 }

Psong