A. Integer Moves
题意：
在平面直角坐标系上存在一个点（x,y），可以进行平移操作，要求每次移动后前后两点的坐标的距离开平方是整数
思路：
整理发现要么一次到位要么就需要两次变化，当然特判一下0的情况
#include<bits/stdc++.h> using namespace std; int main() { int n,i,j,t,a,b; cin>>t; map<int ,int >d1; for(i=0;i<=1050;i++){ d1[i*i]=1; } while(t--) { cin>>a>>b; if(a==0&&b==0) { cout<<0<<endl; } else if(d1[a*a+b*b]!=0) { cout<<1<<endl; } else { cout<<2<<endl; } } return 0; }
B. XY Sequence
题意：
构造一个长度为n的数列，要求他们的和不超过最大，并且单个元素不超过B，且a[i]=a[i-1]+x或者是a[i]=a[i-1]-y。
思路:
贪心的构造只要当前可以取，就想办法取它最大的，可以取的情况介绍a[i]<=B
#include<bits/stdc++.h> using namespace std; const int maxn=2e5+1000; long long a[maxn]; int main() { int n,i,j,t,B,x,y; cin>>t; while(t--) { cin>>n>>B>>x>>y; for(i=0;i<n+1;i++) { if(i==0) a[i]=0; else { if(a[i-1]+x<=B&&a[i-1]-y<=B) { a[i]=max(a[i-1]+x,a[i-1]-y); } else { if(a[i-1]+x>B) { a[i]=a[i-1]-y; } else { a[i]=a[i-1]+x; } } } } long long ans=0; for(i=0;i<n+1;i++) { ans+=a[i]; // cout<<a[i]<<" "; } cout<<ans<<endl; } return 0; }
C. Bracket Sequence Deletion
题意：
给你一个只包含'(', ')'两种字符的字符串，每次操作选择它的最短前缀，如果最短前缀串是回文串或者是可以完成括号匹配的串，就可以进行抵消。
思路：
分析可得，要么最短前缀是(),或者((,))，剩下一种情况就是)开头的，不难发现如果是)开头的，只有当出现第二个），才能完成回文串抵消的操作，而且一定可以将中间全部抵消，所以直接模拟即可。
#include<bits/stdc++.h> using namespace std; bool check(string s2) { for(int i=0;i<s2.length()/2;i++) { if(s2[i]!=s2[s2.length()-i-1]) { return false; } } return true; } int main() { int n,i,j,t; string s1,s2; cin>>t; while(t--) { int f1=0,ans=0; cin>>n>>s1; i=0;s2=""; while(i<n) { s2+=s1[i]; if(s2[0]==')') { if(s1[i]==')') f1++; if(f1==2) { ans++; s2=""; f1=0; } } else { if(s2.length()==2) { ans++; s2=""; f1=0; } } i++; } cout<<ans<<" "<<s2.length()<<endl; } return 0; }
