又是残暴的一场。。。。。竟然3题可以出线我也是醉了。。2题的600+队
全场计算几何，，，
先说说AC的水题：
这个题最大的难度是读题+浮点数处理
For each test case, print the radius of the smallest circle. Please note that the radius must be an POSITIVE INTEGER and no feeding spots should be located just on the circle because it's hard for the campus gardeners to judge whether they are inside or outside the circle. If there are no solution, print "-1" instead.
最关键是这一句话，确定了第二和第四组样例：为什么是2和-1
因为点不能刚好处在圆上
再看看数据，n和m最大100，果断暴力！！！！！
枚举每个点作为圆心，半径就是m个点到该点的从小到大的距离值得第n大向上取整，然后注意判断第n+1大的点会不会在上面
int t,m,n;
double dis[maxn][maxn];
double x[maxn];
double y[maxn];
double temp[maxn];
int main(){
// input;
int i,j,k;
int ans=INF,tempdis;
scanf("%d",&t);
while(t--){
ans=INF;
memset(x,0,sizeof(x));
memset(y,0,sizeof(y));
memset(dis,0,sizeof(dis));
scanf("%d%d",&m,&n);
for(i=1;i<=m;i++) scanf("%lf%lf",&x[i],&y[i]);
for(i=1;i<=m;i++)
for(j=i;j<=m;j++)
dis[j][i]=dis[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
/*for(i=1;i<=m;i++){
for(j=1;j<=m;j++) printf(" %lf",dis[i][j]);
cout<<endl;
}*/
for(i=1;i<=m;i++){ //枚举m个点作为中心点
memset(temp,0,sizeof(temp));
for(j=1;j<=m;j++) temp[j]=dis[i][j];
sort(temp+1,temp+m+1);
if(fabs(temp[n]-(int)temp[n])<eps)
tempdis=ceil(temp[n])+1;
else
tempdis=ceil(temp[n]);
if(fabs(tempdis-temp[n+1])<eps) continue;
//if (int(temp[n+1]==tempdis)) continue;
int number=0;
for(j=1;j<=m;j++)
if (temp[j]+eps<tempdis) number++;
if (number==n) ans=min(ans,tempdis);
}
if (ans==INF) puts("-1");
else printf("%d\n",ans);
}
return 0;
}这个题：看完题意！哇，这么简单的签到。。。打表暴力！
注意其中的细节：Now the designer decides to add a vertical line x=k to this logo( 0<= k < 0.5, and for k, there will be at most 8 digits after the decimal point). He wants to know the number of common points between the new line and the original logo.
最多8位小数，由此知道double会丢失精度！
8位，可以用字符串存储之后转为int（或者long long），由此，变成整数打表就很简单了
ll num,ans,L,R;
int t,len;
char s[100];
ll number[10];
int main(){
//input;
scanf("%d",&t);
while(t--){
num=0;
scanf("%s",s);
len=strlen(s);
for(int i=2;i<len;i++) num=num*10+s[i]-48;
for(int i=len;i<14;i++) num*=10;
number[1]=25;
number[2]=375;
number[3]=4375;
number[4]=46875;
number[5]=484375;
number[6]=4921875;
number[7]=49609375;
number[8]=4980470635;
ans=4;
if (num==500000000000){
puts("1002");
continue;
}
if (num==0){
puts("-1");
continue;
}
ans=1;
L=R=250000000000;
do
{
if (num==R){
ans=-1;
break;
}
if (num>R){
L/=2;
R+=L;
ans++;
}
}
while(num>=R&&L>0);
if (ans==-1) cout<<ans<<endl;
else cout<<4*ans<<endl;
}
return 0;
}本来想打表的。。。后来觉得麻烦，就算了。。。写了个像二分一样的东西
——————————————————————————————————————————————————————————————————————
华丽丽的分割线
学习：
更加优美的bfs暴力：
首先上Final bin的：
int dp[8][900000];
int encode(int a[],int n){
int ret=0;
for(int i=n-1;i>=0;i--){
ret*=n;
ret+=a[i];
}
return ret;
}
void decode(int v,int a[],int n){
for(int i=0;i<n;i++){
a[i]=v%n;
v/=n;
}
}
void gao(int n){
memset(dp[n],-1,sizeof(dp[n]));
int a[10],loc[10];
for(int i=0;i<n;i++) a[i]=i;
int v=encode(a,n);
dp[n][v]=0;
queue<int> q;
q.push(v);
while(!q.empty()){
int st=q.front();
q.pop();
decode(st,a,n);
for(int i=0;i<n;i++) loc[i]=n+1;
for(int i=0;i<n;i++) loc[a[i]]=min(loc[a[i]],i);
for(int i=0;i<n;i++){
if (loc[i]>n) continue;
int tmp=a[loc[i]];
if (i>=1&&loc[i-1]>loc[i]){
a[loc[i]]=i-1;
int tt=encode(a,n);
if (dp[n][tt]==-1){
dp[n][tt]=dp[n][st]+1;
q.push(tt);
}
}
if (i+1<n&&loc[i+1]>loc[i]){
a[loc[i]]=i+1;
int tt=encode(a,n);
if (dp[n][tt]==-1){
dp[n][tt]=dp[n][st]+1;
q.push(tt);
}
}
a[loc[i]]=tmp;
}
}
}
int a[10],b[10];
bool cmp(int i,int j){
return a[i]<a[j];
}
int main(){
memset(dp,-1,sizeof(dp));
for(int i=1;i<8;i++) gao(i);
int T,n;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
b[i]=i;
}
sort(b,b+n,cmp);
int v=encode(b,n);
printf("%d\n",dp[n][v]);
}
return 0;
}再转一个链接：
文档只会有小写字母
首先：文档是空的，只会在最左边有个光标，输入一个，光标就往右一格。
有两种模式：插入和覆盖
大写字母有如下功能：
L：光标左移（可以无操作）
R：光标右移（可以无操作）
S：状态转换：起始状态是插入模式
D：删除：删除在光标右边的一个字符（没有就无操作）
和C还有复合的作用
B：删除：删除在光标左边的一个字符（没有就无操作）
C：复制到剪贴板。首先，剪贴板为空，并且复制状态为“NOTHING”
当C按下时：
如果复制状态为“NOTHING”将被改为“START”并且该光标位置标记为位置1
如果复制状态为“START”将被改为“NOTHING”，并且该光标位置标记为位置2
且两位置间的字符将会被复制到剪贴板
如果，两位置相同，剪贴板清空
注意：当复制状态为“START”时，除了LRD之外的其他字符，复制状态将会立即改为“NOTHING”
而且不影响所有字母的前文表述的功能。
当复制状态为“START”时，如果输入D，复制状态将会立即改为“NOTHING”，并且该光标位置标记为位置2
且两位置间的字符将会被删除
V：将剪贴板中的内容粘贴到光标右侧。如果剪贴板为空，则无操作
在“插入模式”中，粘贴的内容是插入的
在“覆盖模式”中，有k个字符在剪贴板中，那么覆盖k个字符
如果不足，那么剩下的为“插入”
在粘贴之后，光标移动到最后一个被粘贴的字符之后
注意：任何操作不能超过总文本数M个字符
尤其是粘贴操作，要么全部粘贴，要么无操作
比赛的时候从2点钟开始模拟，搞了3个小时以无数个WA和RE收场，，，，真是。。。
学习好了之后回来AC这题
女神的代码借用一下：：：：
#include<map>
#include<set>
#include<math.h>
#include<time.h>
#include<queue>
#include<stack>
#include<cstdio>
#include<string>
#include<cstdlib>
#include<cstring>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
const int maxn=25000;
const int maxm=505;
const int INF=99999999;
#define ll long long
#define eps 1e-6
#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
int main(){
char b[maxn];
crope a,c;
int n,T,mark,mmax,fc,csmark,num;
scanf("%d",&T);
while(T--){
mark=-1;
fc=0;
scanf("%d",&n);
scanf("%s",b);
num=strlen(b);
a.clear();
c.clear();
for(int i=0;i<num;i++){
if (b[i]>='a'&&b[i]<='z'){
if (csmark!=-2) csmark=-2;
if (fc==0||mark+1==a.size()){
if (a.size()>=n) continue;
a.insert(mark+1,b[i]);
mark++;
}
else{
a.erase(mark+1,1);
a.insert(mark+1,b[i]);
mark++;
}
}
else if (b[i]=='R'){
if (mark+1<a.size()) mark++;
}
else if (b[i]=='L'){
if (mark>-1) mark--;
}
else if (b[i]=='S'){
if (csmark!=-2) csmark=-2;
fc=(fc+1)%2;
}
else if (b[i]=='D'){
if (csmark==-2){
if (mark+1<a.size()) a.erase(mark+1,1);
}
else{
if (csmark==mark) csmark=-2;
else if (csmark<mark){
a.erase(csmark+1,mark-csmark);
mark=csmark;
}
else a.erase(mark+1,csmark-mark);
csmark=-2;
}
}
else if (b[i]=='C'){
if (csmark==-2) csmark=mark;
else if (csmark==mark){
csmark=-2;
c.clear();
}
else{
if (csmark<mark) c=a.substr(csmark+1,mark-csmark);
else c=a.substr(mark+1,csmark-mark);
csmark=-2;
}
}
else if (b[i]=='B'){
if (csmark!=-2) csmark=-2;
if (mark>-1){
a.erase(mark,1);
mark--;
}
}
else if (b[i]=='V'){
if (csmark!=-2) csmark=-2;
int mm=a.size()+c.size();
if (fc==0&&mm>n) continue;
mm=mark+1+c.size();
if (fc==1&&mm>n) continue;
for(int j=0;j<c.size();j++){
if (fc==0||mark+1==a.size()){
if (a.size()>=n) continue;
a.insert(mark+1,c.at(j));
mark++;
}
else{
a.erase(mark+1,1);
a.insert(mark+1,c.at(j));
mark++;
}
}
}
}
if (a.size()==0) puts("NOTHING");
else cout<<a<<endl;
}
return 0;
}
京公网安备 11010502036488号