gym 101755
分类:
IT文章
•
2025-02-03 22:57:13
别问我为什么现在才发。。。
我怎么睡醒午觉吃了个饭就晚上九点半了啊？？？？？
真实自闭场，感觉码力严重不足需要补魔。
A：
![]()
1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 ll s,g;
5 int main(){
6 ios::sync_with_stdio(false);
7 cin>>s>>g;
8 if(s%g!=0){
9 cout<<-1;
10 }else if(s==g){
11 cout<<-1;
12 } else{
13 ll tmp = s/g;
14 cout<<g<<' '<<(tmp-1)*g;
15 }
16 }
View Code
B：显然最小的三角形两条边相邻，扫一遍就完了。
![]()
1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef double db;
4 typedef long long ll;
5 const db eps = 1e-6;
6 const db pi = acos(-1);
7 int sign(db k){
8 if (k>eps) return 1; else if (k<-eps) return -1; return 0;
9 }
10 int cmp(db k1,db k2){return sign(k1-k2);}
11 struct point {
12 ll x,y;
13 point operator - (const point &k1) const{return (point){x-k1.x,y-k1.y};}
14 };
15 ll cross(point k1,point k2){return k1.x*k2.y-k1.y*k2.x;}
16 int n;
17 point p[200005];
18 int main(){
19 ios::sync_with_stdio(false);
20 scanf("%d",&n);
21 for(int i=0;i<n;i++){
22 scanf("%lld%lld",&p[i].x,&p[i].y);
23 }
24 ll ans = 4e18;
25 for(int i=0;i<n;i++){
26 ll tmp = cross(p[i]-p[(i+1)%n],p[(i+2)%n]-p[(i+1)%n]);
27 ans=min(ans,abs(tmp));
28 }
29 printf("%lld
",ans);
30 }
View Code
C：贪心选最晚的时刻就完了。
![]()
1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 struct Node{
5 int a,b;
6 }node[200005];
7 bool cmp(Node x,Node y){
8 return x.b<y.b;
9 }
10 int n;
11 vector<int> ans;
12 int main(){
13 scanf("%d",&n);
14 for(int i=1;i<=n;i++){
15 scanf("%d%d",&node[i].a,&node[i].b);
16 }
17 sort(node+1,node+1+n,cmp);
18 int now;
19 for(int l=1,r;l<=n;l=r+1){
20 now = node[l].b;r=l;
21 ans.push_back(now);
22 while (r<n&&node[r+1].a<=now){
23 r++;
24 }
25 }
26 int t = ans.size();
27 printf("%d
",t);
28 for(auto u:ans){
29 printf("%d ",u);
30 }
31 }
View Code
D：
E：
![]()
1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 string s,t;
5 bool slove(int l,int r){
6 while (l<=r){
7 if(s[l]==t[r]&&s[r]==t[l]){
8 } else {
9 return false;
10 }
11 l++,r--;
12 }
13 return true;
14 }
15 int main(){
16 ios::sync_with_stdio(false);
17 cin>>s>>t;
18 if(s==t){
19 cout<<"YES"<<endl;
20 exit(0);
21 }
22 int l=-1,r=-1;
23 for(int i=0;i<s.length();i++){
24 if(s[i]!=t[i]) {
25 l=i;
26 break;
27 }
28 }
29 for(int i=s.length()-1;i>=0;i--){
30 if(s[i]!=t[i]){
31 r=i;
32 break;
33 }
34 }
35 if(slove(l,r))
36 cout<<"YES";
37 else
38 cout<<"NO";
39 }
40 /**
41 adcba
42 adabc
43 */
View Code
F：wa自闭了。。一直wa48。。这个题显然我们可以用一种类似拓扑排序的方式搞。
但是在中间过程要记录一下当前节点的父节点来check，
可以看一下这位大神的题解 https://blog.****.net/v5zsq/article/details/80156734
一是建完图以后看一下是否连的边在原图中都存在。
二是在中间更新父节点的时候，新更新的父节点肯定在之前的父节点(祖先)里。
有点含糊不清。fa其实就是从祖先不断更新一直更新到父节点的这个过程。
![]()
1 #include <bits/stdc++.h>
2 #define pii pair<int,int>
3 #define mk(a,b) make_pair(a,b)
4 using namespace std;
5 typedef long long ll;
6 int n,c,a;
7 int g[1005][1005];
8 int deg[1005],fa[1005];
9 vector<int> v[1005];
10 vector<pii>ans;
11 void gg() { cout << "NO";exit(0); }
12 int main(){
13 ios::sync_with_stdio(false);
14 memset(fa,-1, sizeof(fa));
15 cin>>n;
16 for(int i=1;i<=n;i++){
17 cin>>c;
18 while (c--){
19 cin>>a;
20 g[i][a]=1;
21 v[i].push_back(a);
22 deg[a]++;
23 }
24 }
25 queue<int> q;
26 for(int i=1;i<=n;i++)
27 if(deg[i]==0)q.push(i);
28 if(q.size()!=1)gg();
29 int rt=q.front();
30 while (!q.empty()){
31 int x = q.front();
32 q.pop();
33 for(auto u:v[x]){
34 deg[u]--;
35 if(fa[u]!=-1&&!g[fa[u]][x]){//新的祖先必然要以之前的祖先为祖先
36 gg();
37 }
38 fa[u]=x;
39 if(deg[u]==0){
40 q.push(u);
41 ans.push_back(mk(x,u));
42 }
43 }
44 }
45 for(int i=1;i<=n;i++){
46 if(i==rt)continue;
47 for(auto u:v[i]){
48 if(!g[fa[i]][u])gg();
49 }
50 }
51 if(ans.size()==n-1){
52 cout<<"YES"<<endl;
53 for(auto tmp:ans){
54 cout<<tmp.first<<' '<<tmp.second<<endl;
55 }
56 } else {
57 gg();
58 }
59 }
View Code
H：bfs。要注意的是判断能不能走的时候每个点被更新的次数是很少的所以不会T。
看到有大神说至多两次。。。不太清楚。。。
![]()
1 #include <bits/stdc++.h>
2 #define pii pair<int,int>
3 #define mk(a,b) make_pair(a,b)
4 using namespace std;
5 typedef long long ll;
6 const int N = 2e5+5;
7 int n,m,d;
8 bool in(int x,int y){
9 return x>=1&&y>=1&&x<=n&&y<=m;
10 }
11 int main(){
12 ios::sync_with_stdio(false);
13 cin>>n>>m>>d;
14 char s[n+1][m+1];
15 int vis[n+1][m+1];
16 int val[n+1][m+1];
17 memset(vis,0, sizeof(vis));
18 memset(val,0, sizeof(val));
19 queue<pii> q;
20 pii u,v;
21 for(int i=1;i<=n;i++){
22 for(int j=1;j<=m;j++) {
23 cin >> s[i][j];
24 if(s[i][j]=='S') u=mk(i,j);
25 else if(s[i][j]=='F') v=mk(i,j);
26 else if(s[i][j]=='M') {
27 q.push(mk(i,j));vis[i][j]=1;
28 }
29 }
30 }
31 while (!q.empty()){
32 int x = q.front().first,y=q.front().second;
33 q.pop();
34 if(in(x-1,y)&&!vis[x-1][y]&&val[x][y]<d){
35 vis[x-1][y]=1;
36 val[x-1][y]=val[x][y]+1;
37 q.push(mk(x-1,y));
38 }
39 if(in(x+1,y)&&!vis[x+1][y]&&val[x][y]<d){
40 vis[x+1][y]=1;
41 val[x+1][y]=val[x][y]+1;
42 q.push(mk(x+1,y));
43 }
44 if(in(x,y-1)&&!vis[x][y-1]&&val[x][y]<d){
45 vis[x][y-1]=1;
46 val[x][y-1]=val[x][y]+1;
47 q.push(mk(x,y-1));
48 }
49 if(in(x,y+1)&&!vis[x][y+1]&&val[x][y]<d){
50 vis[x][y+1]=1;
51 val[x][y+1]=val[x][y]+1;
52 q.push(mk(x,y+1));
53 }
54 }
55 if(vis[u.first][u.second]){
56 return 0*printf("-1
");
57 }
58 while (!q.empty()) q.pop();
59 q.push(u);
60 memset(val,0, sizeof(val));
61 while (!q.empty()){
62 int x=q.front().first,y=q.front().second;
63 q.pop();
64 if(in(x,y+1)&&!val[x][y+1]&&!vis[x][y+1]){
65 val[x][y+1]=val[x][y]+1;
66 q.push(mk(x,y+1));
67 }
68 if(in(x,y-1)&&!val[x][y-1]&&!vis[x][y-1]){
69 val[x][y-1]=val[x][y]+1;
70 q.push(mk(x,y-1));
71 }
72 if(in(x+1,y)&&!val[x+1][y]&&!vis[x+1][y]){
73 val[x+1][y]=val[x][y]+1;
74 q.push(mk(x+1,y));
75 }
76 if(in(x-1,y)&&!val[x-1][y]&&!vis[x-1][y]){
77 val[x-1][y]=val[x][y]+1;
78 q.push(mk(x-1,y));
79 }
80 }
81 if(val[v.first][v.second])
82 printf("%d
",val[v.first][v.second]);
83 else
84 printf("-1
");
85 }
View Code
J：
![]()
1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 const int N = 200005;
5 int n,x,a[N];
6 int main(){
7 ios::sync_with_stdio(false);
8 cin>>n;
9 for(int i=1;i<=n;i++){
10 cin>>x;a[x]++;
11 }
12 int ans = 0;
13 for(int i=1;i<=200000;i++){
14 ans+=a[i]/2;
15 }
16 ans/=2;
17 cout<<ans<<endl;
18 }
View Code
K：显然二分，然后我们贪心的选就可以了。
![]()
1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 int n,m;
5 int a[200005];
6 int check(int x){
7 int res=0;
8 for(int i=1;i<=n;i++){
9 if(a[i]<=res){
10 res++;
11 } else if(a[i]>res&&x>0){
12 x--;
13 res++;
14 }
15 }
16 return res;
17 }
18 int main(){
19 ios::sync_with_stdio(false);
20 cin>>n>>m;
21 for(int i=1;i<=n;i++){
22 cin>>a[i];
23 }
24 int l=0,r=n,ans=m;
25 while (l<=r){
26 int mid = l+r>>1;
27 if(check(mid)>=m){
28 r=mid-1;
29 ans=mid;
30 } else{
31 l=mid+1;
32 }
33 }
34 cout<<ans;
35 }
View Code
L：严重码力不足，，其实挺好想的，我们维护s串第i个位置下一个j字母的位置就可以了。
但是当时没写。。。貌似在专心自闭F。。。
![]()
1 #include <bits/stdc++.h>
2 using namespace std;
3 const int N = 200005;
4 int nxt[N][26],pos[26],q;
5 char s[N],op[7];
6 int ans[N];
7 int main(){
8 scanf("%s",s+1);
9 int n = strlen(s+1);
10 memset(nxt,-1, sizeof(nxt));
11 memset(pos,-1, sizeof(pos));
12 for(int i=n;i>=0;i--){
13 for(int j=0;j<26;j++)
14 nxt[i][j]=pos[j];
15 pos[s[i]-'a']=i;
16 }
17 scanf("%d",&q);
18 int m=0,len=0;
19 while (q--){
20 scanf("%s",op);
21 if(op[1]=='o'){//
22 m--;len=min(len,m);
23 } else{
24 scanf("%s",op);
25 if(ans[m]!=-1&&nxt[ans[m]][op[0]-'a']!=-1) {
26 ans[m+1]=nxt[ans[m]][op[0]-'a'];
27 m++;len++;
28 } else{
29 ans[++m]=-1;
30 }
31 }
32 if(len==m)printf("YES
");
33 else printf("NO
");
34 }
35 }
36 /**
37 abcabc
38 4
39 push a
40 push a
41 push a
42 push a
43 */
View Code
M：
还是上面那个大神的 https://blog.****.net/v5zsq/article/details/80168485
这种小模拟思路清晰非常重要，然后我当时大概神志不清？？反正就是不想写(雾
![]()
1 #include <bits/stdc++.h>
2 using namespace std;
3 string a,b,c;int n;
4 vector<int> v;
5 bool check(){
6 int num=0;
7 for(int i=0;i<n;i++){
8 if(b[i]!=a[i])num++;
9 if(num>1)return 0;
10 }
11 num=0;
12 for(int i=0;i<n;i++){
13 if(c[i]!=a[i])num++;
14 if(num>1)return 0;
15 }
16 return 1;
17 }
18 int main(){
19 ios::sync_with_stdio(false);
20 cin>>a>>b>>c;n=a.length();
21 for(int i=0;i<n;i++){
22 if(a[i]!=b[i]||a[i]!=c[i])v.push_back(i);
23 }
24 if(v.size()>3){
25 cout<<"Impossible"<<endl;
26 return 0;
27 }
28 if(v.size()==0){
29 cout<<"Ambiguous"<<endl;
30 return 0;
31 }
32 int ans = 0;
33 int pos,x;
34 if (check()){
35 ans++;
36 x=a[0];pos=0;
37 }
38 bool f=1;
39 for(auto id:v){
40 char tmp = a[id];
41 for(int i=0;i<26;i++){
42 if(tmp==char('a'+i))continue;
43 a[id]=char('a'+i);
44 if(check()){
45 ans++;pos=id,x=char('a'+i);
46 //cout<<id<<' '<<char('a'+i)<<endl;
47 }
48 }
49 a[id]=tmp;
50 }
51
52 if(ans==0){
53 cout<<"Impossible
";
54 } else if(ans>1){
55 cout<<"Ambiguous"<<endl;
56 } else{
57 a[pos]=x;
58 cout<<a;
59 }
60 }
View Code
为什么好友单切全都9题10题啊？我才6题啊好尴尬啊。。。
