24
牛客多校第三场
source link: http://www.cnblogs.com/rair/p/13338961.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
A.Clam and Fish
思路:贪心,没啥好说
int n,m,k; string s; void solve(){ cin>>n; cin>>s; int f=0,c=0; for (int i=0;i<n;i++){ if (s[i]=='0'){ if (c)c--,f++; } else if (s[i]=='1')c++; else f++; } f+=c/2; cout<<f<<endl; } int main(){ int T=1; cin>>T; while (T--){ solve(); } return 0; }
B.Classical String Problem
思路:记录头指针
int n,m,k,p; string s; void solve(){ char c; int x; getchar(); scanf("%c %d",&c,&x); if (c=='M'){ p=(p+x+k)%k; } else{ printf("%c\n",s[(p+x-1)%k]); } } int main(){ int T=1; cin>>s; k=s.size(); p=0; cin>>T; while (T--){ solve(); } return 0; }
C.Operation Love
题意:
将这只任意翻转旋转过的手的20个坐标顺时针或逆时针给你,问是左手还是右手
思路:先用叉积判断出给出顺逆时针,再通过边长的关系得出左手还是右手
#define sqr(a) (a)*(a) const double eps=0.1; string s; double x[21],y[21]; void solve(){ for (int i=0;i<20;i++)scanf("%lf%lf",&x[i],&y[i]); double ans=0; for (int i=0;i<20;i++)ans+=x[i]*y[(i+1)%20]-x[(i+1)%20]*y[i];//鞋带公式 ans/=2;//面积,<0顺时针,>0逆时针 int a,b; for (int i=0;i<20;i++){ double t=sqrt(sqr(x[i]-x[(i+1)%20])+sqr(y[i]-y[(i+1)%20])); if (t<=9+eps&&t>=9-eps)a=i; if (t<=8+eps&&t>=8-eps)b=i; } if ((a<b&&!(a==0&&b==19))||(a==19&&b==0)){ if (ans>0) puts("right"); else puts("left"); } else{ if (ans>0) puts("left"); else puts("right"); } } int main(){ int T=1; cin>>T; while (T--){ solve(); } return 0; }
D.Points Construction Problem
题意:给定n,m,n代表n个黑点,m代表黑点和周围空白区域构成的黑白点对个数,问满足n和m图形能否构成
思路:分析得,一个凸的黑点构成的图形形成的点对为其外长方形的周长,也易知,m为奇数,该图形无法构成。
不妨令所有点外围为同一个长方形
最少点构成最大图形
最多点构成图形为长方形整体
中间部分的点可以如图补充,左边同右边
可以枚举1-m/2,长宽为a,b,当点在max(a,b)<=n<=a*b时满足
int n,m,k; void solve(){ cin>>n>>m; if (m&1){cout<<"No"<<endl;return;} bool f=0; int a,b; for (int i=1;i<=m/2/2;i++){//枚举长宽的宽 a=i,b=m/2-i; if (n>=b&&n<=a*b){f=1;break;} } if (f==0){cout<<"No"<<endl;return;} cout<<"Yes"<<endl; n-=b; for (int i=1;i<=a;i++)printf("%d %d\n",i,i); for (int i=a+1;i<=b;i++)printf("%d %d\n",a,i); for (int i=a-1;i>=1;i--){ if (n==0)break; for (int j=i+1;j<=b;j++){ printf("%d %d\n",i,j); n--; if (n==0)break; } } for (int i=2;i<=a;i++){ if (n==0)break; for (int j=i-1;j>=1;j--){ printf("%d %d\n",i,j); n--; if (n==0)break; } } } int main(){ int T=1; cin>>T; while (T--){ solve(); } return 0; }
E.Two Matchings
题意:原序列为a,长度为n,n为偶数,寻找两个置换序列p,q,满足a[p[i]]!=i,a[p[p[i]]]=i,问
的最小值
思路:只要满足4个点及以上一组就必定能形成2个置换序列,值为组中的(max-min)*2,先排序,再利用动态规划即可求出最小值
int n,m,k; int a[N],dp[N]; void solve(){ cin>>n; for (int i=1;i<=n;i++)scanf("%d",&a[i]); sort(a+1,a+1+n); for (int i=1;i<=n;i++)dp[i]=inf; dp[0]=0; for (int i=4;i<=n;i++){ dp[i]=min(dp[i],dp[i-4]+a[i]-a[i-3]); dp[i]=min(dp[i],dp[i-2]+a[i]-a[i-2]); } cout<<dp[n]*2<<endl; } int main(){ int T=1; cin>>T; while (T--){ solve(); } return 0; }
F.Fraction Construction Problem
G.Operating on a Graph
H.Sort the Strings Revision
I.Sorting the Array
J.Operating on the Tree
K.Eleven Game
L.Problem L is the Only Lovely Problem
超级签到题
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK