2018GPLT (天梯赛训练03-01)
1.天梯赛座位分配
这题在网上都没找到篇靠谱的解答 很多都是错的 （可能但凡会点编程的人都不会被这题卡住了吧）（悲）
从我的好朋友毛的程序 我觉得非常清晰 顺便再吐槽一点：我的模拟怎么办啊~
int a[N];
vector<int>ans[N];
void solve(){
int n=read(),cnt=n,tt=1; //cnt记录学校数 我觉得这是灵魂 tt计数
for(int i=1;i<=n;i++){
a[i]=read()*10; //记录每个学校的人数
}
while(cnt){ //有学校没分完
for(int i=1;i<=n;i++){ //每个学校轮流
if(a[i]){ //如果还有人
ans[i].push_back(tt++); //加入答案中
if(cnt==1)tt++; //只剩一个学校就+2
a[i]--; //学校的人数被分配 --
if(!a[i])cnt--; //一个学校被全分完 cnt--
}
}
}
for(int i=1;i<=n;i++){ //按格式输出罢了
int hh=0;
cout<<"#"<<i<<endl;
for(int x:ans[i]){
cout<<x;
hh++;
if(hh%10) cout<<" ";
else {
cout<<endl;
hh=0;
}
}
}
}
2.倒数第N个字符串
关于反转字符串的前导字符或者前导零的问题 在大一上的一次月考被狠狠的搞了 但是还是没记住 希望下次能记着好吧 (悲)
int ans[N];
void solve(){
int n=read(),m=read();
int p=pow(26,n)-m;
for(int i=0;i<n;i++){
ans[i]=p%26;
p/=26;
}
for(int j=n-1;j>=0;j--){
char x=ans[j]+'a';
cout<<x;
}
}
10.小字辈
带权并查集一直写不好 趁这个机会好好背一下板子
int p[N], d[N];
int find(int x)
{
if (p[x] != x)
{
int u = find(p[x]);
d[x] += d[p[x]];
p[x] = u;
}
return p[x];
}
void solve(){
int n=read(),maxx=0;
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
d[i] = 0; //这个板子必须初始化为零
}
for(int i=1;i<=n;i++){
int y=read();
if(y!=-1){ //这里的合并记一下
p[find(i)]=find(y);
d[i]=1+d[y];
}
}
for(int i=1;i<=n;i++){
find(i);
maxx=max(maxx,d[i]);
}
cout<<maxx+1<<endl;
vector<int>ans;
for(int i=1;i<=n;i++){
find(d[i]);
if(d[i]==maxx)ans.push_back(i);
}
for(int i=0;i<ans.size();i++){
cout<<ans[i];
if(i!=ans.size()-1)cout<<" ";
}
}
12.秀恩爱分得快
大模拟罢了！（哭腔）
int gender[1008];
vector<vector<int> > v;
int read(string s){
int len=s.length(),num=0;
int flag=1;
if(s[0]=='-') flag=0;
else num=s[0]-'0';
for(int i=1;i<len;i++){
num=num*10+s[i]-'0';
}
gender[num]=flag;
return num;
}
void solve(){
int n=read(),m=read(),k;
string t;
v.resize(n);
vector<double> pa(n,0.0);
vector<double> pb(n,0.0);
for(int i=0;i<m;i++){
k=read();
v[i].resize(k);
for(int j=0;j<k;j++){
cin>>t;
int num=read(t);
v[i][j]=num;
}
}
string a,b;
cin>>a>>b;
int a1=read(a),b1=read(b);
double mxa=0,mxb=0;
for(int i=0;i<m;i++){
bool fa=find(v[i].begin(),v[i].end(),a1)!=v[i].end();
bool fb=find(v[i].begin(),v[i].end(),b1)!=v[i].end();
if(fa||fb){
for(int j=0;j<v[i].size();j++){
if(fa){
if(gender[v[i][j]]+gender[a1]==1){
pa[v[i][j]]+=1.0/v[i].size();
mxa=max(mxa,pa[v[i][j]]);
}
}
if(fb){
if(gender[v[i][j]]+gender[b1]==1){
pb[v[i][j]]+=1.0/v[i].size();
mxb=max(mxb,pb[v[i][j]]);
}
}
}
}
}
if(pa[b1]==mxa&&pb[a1]==mxb){
printf("%s%d %s%d\n",gender[a1]?"":"-",a1,gender[b1]?"":"-",b1);
}else{
for(int i=0;i<n;i++){
if(pa[i]==mxa){
printf("%s%d %s%d\n",gender[a1]?"":"-",a1,gender[a1]?"-":"",i);
}
}
for(int i=0;i<n;i++){
if(pb[i]==mxb){
printf("%s%d %s%d\n",gender[b1]?"":"-",b1,gender[b1]?"-":"",i);
}
}
}
}
13.代码排版
也是大模拟罢了！（大哭腔） 这种模拟 我选择直接放弃
int judge(string dat, int i){ //判断语句块类型
//WA3:当前位置是if并且不是在字符串内
if(dat.find("if", i)==i && (dat[i+2]==' '||dat[i+2]=='('))return 2;
if(dat.find("for",i)==i && (dat[i+3]==' ' ||dat[i+3]=='('))return 3;
if(dat.find("while",i)==i && (dat[i+5]==' '||dat[i+5]=='('))return 5;
if(dat.find("else",i)==i && dat[i+4]==' ')return 4;
return 0; //普通语句
}
//输出前删除多余空格, 并输出当前对应的空格
void erase_space(string dat,int &i){while(dat[i]==' ')i++;}
void print_space(int sp){for(int i=0;i<sp;i++)putchar(' ');}
void solve(){
string dat; getline(cin,dat);
//处理int main() 找i和)输出
int l = dat.find('i',0), r = dat.find(')',0);
cout<<dat.substr(l,r-l+1)<<"\n{\n";
//处理其他，按照行分类
int tmp, space = 2; //语句类型,空格数
int flag, debt=0; //单句标记，层数（补全缺少的}）
for(int i = dat.find('{')+1,j=0,k; i < dat.size(); ){
erase_space(dat,i);//删除每行前的空格
if(dat[i]=='{' || dat[i]=='}'){
if(dat[i]=='{'){
print_space(space);
printf("{\n");
space += 2;
i++;
continue;
}
else{
space -= 2;
print_space(space);
printf("}\n");
i++;
if(space==0)break;//main的}输完就结束了
//【重复】单句特判
erase_space(dat,i);
while(debt && judge(dat,i)!=4){
space -= 2;
print_space(space);
printf("}\n");
debt--;
}
}
}else if((tmp=judge(dat,i))){
print_space(space);
//处理for,while,if,+()或者else
if(tmp==4){
printf("else");
k = i+3;
}else{
cout<<dat.substr(i,tmp)<<" ";
i += tmp;
erase_space(dat, i);
//考虑if()中也有()条件的情况
k = i; int t = 0;
while(1){
if(dat[k]=='(')t++;
if(dat[k]==')')t--;
if(!t)break;
k++;
}
cout<<dat.substr(i,k-i+1);
}
//预处理{}的内容,考虑单句特判
int m = k+1;
erase_space(dat,m);
if(dat[m] != '{'){ //单句标记
printf(" {\n");
flag = 1;
debt++;
i = m;
}
else{
printf(" {\n");
flag = 0;
i = m+1;
}
space += 2;
}else{
int ed = dat.find(';', i); //普通语句
print_space(space);
cout<<dat.substr(i,ed-i+1)<<"\n";
i = ed+1;
if(flag && debt){ //这是单句内的语句
space -= 2;
print_space(space);
printf("}\n");
debt--;
erase_space(dat,i); //【重复】单句特判
while(debt && judge(dat,i)!=4){
space -= 2;
print_space(space);
printf("}\n");
debt--;
}
}
}
}
return ;
}
14.至多删三个字符
dp的去重 目前还没怎么见到过 学习一下（感觉不可能想出来的）
int dp[N][4];
void solve(){
string str;
cin>>str;
int n=str.size();
str=' '+str;
dp[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<=3;j++){
dp[i][j]=dp[i-1][j]; //dp i:当前位置 j:删掉几个 若当前不删则继承[i-1][j] 若删需格外继承[i-1][j-1]
if(j)dp[i][j]+=dp[i-1][j-1];
for(int h=i-1;h>=1&&i-h<=j;h--){
if(str[h]==str[i]){ /*去重:在i-h<=j时 若有str[h]==str[i] 则在此区间[h-i]删掉两个相同的字符
效果相同 需要去掉相同的部分*/
dp[i][j]-=dp[h-1][j-(i-h)];
break;
}
}
}
}
int ans=0;
for(int i=0;i<=3;i++){
ans+=dp[n][i];
}
cout<<ans<<endl;
}
15.神坛
bool cmp (const pair<long long, long long> &a, const pair<long long, long long> &b) {
if (a.first * b.second != b.first * a.second)
return a.first * b.second > b.first * a.second;
return a.first < b.first;
}
void solve(){
int n=read(),cnt=0,ans=INF;
vector<pair<long long, long long>> A(n), B(n - 1);
for (int i = 0; i < n; i++) scanf("%lld %lld", &A[i].first, &A[i].second);
for (int i = 0; i < n; i++, cnt = 0) {
for (int j = 0; j < n; j++) {
if (i == j) continue;
B[cnt++] = {A[j].first - A[i].first, A[j].second - A[i].second};
}
sort(B.begin(), B.end(), cmp);
for (int j = 1; j < n - 1; ++j) ans = min(ans, abs(B[j - 1].first * B[j].second - B[j].first * B[j - 1].second));
}
printf("%.3f", 0.5 * ans);
return;
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
标签：03,01,2018GPLT,int,dat,read,second,return,first
From： https://www.cnblogs.com/edgrass/p/17169883.html