Openjudge百练机试练习

目录：日期+题号+题目大意+题解+总结

2021.1.16

1002：方便记忆的电话号码

题目大意：给出字母和数字的映射关系和一串字母和数字，对于每个串输出格式化后的数字串

用位运算的思路从后往前将字符串转成int，用map存储+排序

#include<cstdio>
#include<string>
#include<map>
#include<algorithm>
#include<iostream>
using namespace std;
int n,Pow[10],tot;
string s;
map<int,int>G;
struct data
{
	int val,count;
}a[100010];

int get(char x)
{
	if (x>='A' && x<='C' || x>='a' && x<='c') return 2;
	if (x>='D' && x<='F' || x>='d' && x<='f') return 3;
	if (x>='G' && x<='I' || x>='g' && x<='i') return 4;
	if (x>='J' && x<='L' || x>='j' && x<='l') return 5;
	if (x>='M' && x<='O' || x>='m' && x<='o') return 6;
	if (x>='P' && x<='S' || x>='p' && x<='s') return 7;
	if (x>='T' && x<='V' || x>='t' && x<='v') return 8;
	if (x>='W' && x<='Y' || x>='w' && x<='y') return 9;
}

bool cmp(data x,data y)
{
	return x.val<y.val;
}

int main()
{
	scanf("%d",&n),Pow[0]=1;
	for (int i=1;i<=7;++i) Pow[i]=Pow[i-1]*10;
	for (int i=1;i<=n;++i)
	  {
	  	cin>>s;
	  	int bit=0,num=0;
	  	for (int j=s.length()-1;j>=0;--j)
	  	  if (s[j]>='0' && s[j]<='9') num+=(s[j]-'0')*Pow[bit],++bit;
	  	  else if (s[j]>='A' && s[j]<='Z' || s[j]>='a' && s[j]<='z') num+=get(s[j])*Pow[bit],++bit;
	  	++G[num];
	  }
	for (map<int,int>::iterator i=G.begin();i!=G.end();++i) a[++tot]=(data){i->first,i->second};
	sort(a+1,a+tot+1,cmp);
	bool flag=false;
	for (int i=1;i<=tot;++i)
	  if (a[i].count>1) printf("%03d-%04d %d\n",a[i].val/10000,a[i].val%10000,a[i].count),flag=true;
	if (!flag) printf("No duplicates.");
	return 0;
}

#include<cstdio>

#include<string>

#include<map>

#include<algorithm>

#include<iostream>

using namespace std;

int n,Pow[10],tot;

string s;

map<int,int>G;

struct data

{

int val,count;

}a[100010];

int get(char x)

{

if (x>='A' && x<='C' || x>='a' && x<='c') return 2;

if (x>='D' && x<='F' || x>='d' && x<='f') return 3;

if (x>='G' && x<='I' || x>='g' && x<='i') return 4;

if (x>='J' && x<='L' || x>='j' && x<='l') return 5;

if (x>='M' && x<='O' || x>='m' && x<='o') return 6;

if (x>='P' && x<='S' || x>='p' && x<='s') return 7;

if (x>='T' && x<='V' || x>='t' && x<='v') return 8;

if (x>='W' && x<='Y' || x>='w' && x<='y') return 9;

}

bool cmp(data x,data y)

{

return x.val<y.val;

}

int main()

{

scanf("%d",&n),Pow[0]=1;

for (int i=1;i<=7;++i) Pow[i]=Pow[i-1]*10;

for (int i=1;i<=n;++i)

{

cin>>s;

int bit=0,num=0;

for (int j=s.length()-1;j>=0;--j)

if (s[j]>='0' && s[j]<='9') num+=(s[j]-'0')*Pow[bit],++bit;

else if (s[j]>='A' && s[j]<='Z' || s[j]>='a' && s[j]<='z') num+=get(s[j])*Pow[bit],++bit;

++G[num];

}

for (map<int,int>::iterator i=G.begin();i!=G.end();++i) a[++tot]=(data){i->first,i->second};

sort(a+1,a+tot+1,cmp);

bool flag=false;

for (int i=1;i<=tot;++i)

if (a[i].count>1) printf("%03d-%04d %d\n",a[i].val/10000,a[i].val%10000,a[i].count),flag=true;

if (!flag) printf("No duplicates.");

return 0;

}

总结：①pow在algorithm头文件中是个函数，不能当作变量名用，会CE②题目描述中举的例子也要测试，这里就没注意到也可能存在小写字母③转成int可能存在前导零的现象，对于前三位和后四位都要格式化输出，%0id表示限制输出为i位，不足补前导零

1007：DNA排序

题目大意：给出一坨字母串，求逆序对然后根据逆序对数排序

因为数据范围实在太小懒得用树状数组了，直接上二重循环统计排序

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<string>
using namespace std;
int n,m;
string s[110];
struct data
{
	int id,num;
}a[110];

bool cmp(data x,data y)
{
	return x.num==y.num?x.id<y.id:x.num<y.num;
}

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;++i) 
	  {
	  	cin>>s[i],a[i].id=i;
	  	for (int j=1;j<n;++j)
	  	  for (int k=0;k<j;++k)
	  	    if (s[i][k]>s[i][j]) ++a[i].num;
	  }
	sort(a+1,a+m+1,cmp);
	for (int i=1;i<=m;++i) cout<<s[a[i].id]<<endl;
	return 0;
}

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<string>

using namespace std;

int n,m;

string s[110];

struct data

{

int id,num;

}a[110];

bool cmp(data x,data y)

{

return x.num==y.num?x.id<y.id:x.num<y.num;

}

int main()

{

scanf("%d%d",&n,&m);

for (int i=1;i<=m;++i)

{

cin>>s[i],a[i].id=i;

for (int j=1;j<n;++j)

for (int k=0;k<j;++k)

if (s[i][k]>s[i][j]) ++a[i].num;

}

sort(a+1,a+m+1,cmp);

for (int i=1;i<=m;++i) cout<<s[a[i].id]<<endl;

return 0;

}

总结：①写的过程中把s[i][k]>s[i][j]写成s[k]>s[j]没看出来，是该多练练了

2021.1.17

1017：装箱问题

题目大意：给出1*1、2*2、3*3、4*4、5*5、6*6规格的物品装进6*6的箱子里，物品和箱子等高，求最少需要几个箱子

贪心，先装大的，装大的同时尽可能装小的，因为物品和箱子等高，可以转化为二维平面的填充问题

#include<cstdio>
using namespace std;
int a[7];
int main()
{
	while (1)
	  {
	  	int ans=0;
	  	bool flag=true;
	  	for (int i=1;i<=6;++i) 
	  	  {
	  	  	scanf("%d",&a[i]);
	  	  	if (a[i]) flag=false;
		  }
	  	if (flag) break;
	  	ans+=a[6];
	  	for (int i=1;i<=a[5];++i)
	  	  {
	  	  	++ans;
	  	  	if (a[1]>=11) a[1]-=11;
	  	  	else a[1]=0;
		  }
		for (int i=1;i<=a[4];++i)
		  {
		  	++ans;
		  	if (a[2]>=5) a[2]-=5;
		  	else 
		  	  {
		  	  	int num=20-a[2]*4;
		  	  	a[2]=0;
		  	  	if (a[1]>=num) a[1]-=num;
		  	  	else a[1]=0;
			  }
		  }
		ans+=a[3]/4,a[3]%=4;
		if (a[3])
		  {
		  	++ans;
		  	if (a[3]==1)
		  	  {
		  	  	int num1=7,num2=5;
		  	  	if (a[2]>=num2) a[2]-=num2;
		  	  	else num1+=(num2-a[2])*4,a[2]=0;
		  	  	if (a[1]>=num1) a[1]-=num1;
		  	  	else a[1]=0;
			  }
			if (a[3]==2)
			  {
			  	int num1=6,num2=3;
			  	if (a[2]>=num2) a[2]-=num2;
		  	  	else num1+=(num2-a[2])*4,a[2]=0;
		  	  	if (a[1]>=num1) a[1]-=num1;
		  	  	else a[1]=0;
			  }
			if (a[3]==3)
			  {
			  	int num1=5,num2=1;
			  	if (a[2]>=num2) a[2]-=num2;
		  	  	else num1+=(num2-a[2])*4,a[2]=0;
		  	  	if (a[1]>=num1) a[1]-=num1;
		  	  	else a[1]=0;
			  }
		  }
		while (a[2])
		  {
		  	++ans;
		  	if (a[2]>=9) a[2]-=9;
		  	else if (a[1]>=36-a[2]*4) a[1]-=36-a[2]*4,a[2]=0;
		  	else a[1]=a[2]=0;
		  }
		while (a[1])
		  {
		  	++ans;
		  	if (a[1]>=36) a[1]-=36;
		  	else a[1]=0;
		  }
		printf("%d\n",ans);
	  }
	return 0;
}

#include<cstdio>

using namespace std;

int a[7];

int main()

{

while (1)

{

int ans=0;

bool flag=true;

for (int i=1;i<=6;++i)

{

scanf("%d",&a[i]);

if (a[i]) flag=false;

}

if (flag) break;

ans+=a[6];

for (int i=1;i<=a[5];++i)

{

++ans;

if (a[1]>=11) a[1]-=11;

else a[1]=0;

}

for (int i=1;i<=a[4];++i)

{

++ans;

if (a[2]>=5) a[2]-=5;

else

{

int num=20-a[2]*4;

a[2]=0;

if (a[1]>=num) a[1]-=num;

else a[1]=0;

}

ans+=a[3]/4,a[3]%=4;

if (a[3])

{

++ans;

if (a[3]==1)

{

int num1=7,num2=5;

if (a[2]>=num2) a[2]-=num2;

else num1+=(num2-a[2])*4,a[2]=0;

if (a[1]>=num1) a[1]-=num1;

else a[1]=0;

}

if (a[3]==2)

{

int num1=6,num2=3;

if (a[2]>=num2) a[2]-=num2;

else num1+=(num2-a[2])*4,a[2]=0;

if (a[1]>=num1) a[1]-=num1;

else a[1]=0;

}

if (a[3]==3)

{

int num1=5,num2=1;

if (a[2]>=num2) a[2]-=num2;

else num1+=(num2-a[2])*4,a[2]=0;

if (a[1]>=num1) a[1]-=num1;

else a[1]=0;

}

while (a[2])

{

++ans;

if (a[2]>=9) a[2]-=9;

else if (a[1]>=36-a[2]*4) a[1]-=36-a[2]*4,a[2]=0;

else a[1]=a[2]=0;

}

while (a[1])

{

++ans;

if (a[1]>=36) a[1]-=36;

else a[1]=0;

}

printf("%d\n",ans);

}

return 0;

}

1035：拼写检查

题目大意：给出一个词典，再给出一坨单词，判断单词是否在词典中或者单词是否与词典中的词相似（相差不多于一个字符，相差即为增删改）

大体算了一下时间复杂度可以暴力，计算单词相似度采用双指针，遇到不一样的跳过，不一样的个数超过一个即为不相似

#include<cstdio>
#include<string>
#include<iostream>
using namespace std;
string s[10010],t;
int n;

bool check_equal(string x)
{
	for (int i=1;i<=n;++i)
	  if (s[i]==x) return true;
	return false;
}

int Abs(int x)
{
	return x>0?x:-x;
}

void check_similar(string x)
{
	cout<<": ";
	for (int i=1;i<=n;++i)
	  if (s[i].length()==x.length())
	    {
	    	int count=0;
	    	for (int j=0;j<x.length();++j)
	    	  if (s[i][j]!=x[j]) ++count;
	    	if (count<=1) cout<<s[i]<<" ";
		}
	  else if (Abs(s[i].length()-x.length())==1)
	    {
	    	int count=0,headx=0,heads=0;
	    	while (headx!=x.length() && heads!=s[i].length())
	    	  {
	    	  	if (s[i][heads]==x[headx]) ++headx,++heads;
	    	  	else 
	    	  	  {
	    	  	  	++count;
	    	  	  	if (s[i].length()>x.length()) ++heads;
	    	  	  	else ++headx;
				  }
			  }
			if (count<=1) cout<<s[i]<<" ";
		}
	cout<<endl;
}

int main()
{
	while (1)
	  {
	  	cin>>s[++n];
	  	if (s[n]=="#")
	  	  {
	  	  	--n;
	  	  	break;
		  }
	  }
	while (1)
	  {
	  	cin>>t;
	  	if (t=="#") break;
	  	cout<<t;
	  	if (check_equal(t)) cout<<" is correct"<<endl;
	  	else check_similar(t);
	  }
	return 0;
}

#include<cstdio>

#include<string>

#include<iostream>

using namespace std;

string s[10010],t;

int n;

bool check_equal(string x)

{

for (int i=1;i<=n;++i)

if (s[i]==x) return true;

return false;

}

int Abs(int x)

{

return x>0?x:-x;

}

void check_similar(string x)

{

cout<<": ";

for (int i=1;i<=n;++i)

if (s[i].length()==x.length())

{

int count=0;

for (int j=0;j<x.length();++j)

if (s[i][j]!=x[j]) ++count;

if (count<=1) cout<<s[i]<<" ";

}

else if (Abs(s[i].length()-x.length())==1)

{

int count=0,headx=0,heads=0;

while (headx!=x.length() && heads!=s[i].length())

{

if (s[i][heads]==x[headx]) ++headx,++heads;

else

{

++count;

if (s[i].length()>x.length()) ++heads;

else ++headx;

}

if (count<=1) cout<<s[i]<<" ";

}

cout<<endl;

}

int main()

{

while (1)

{

cin>>s[++n];

if (s[n]=="#")

{

--n;

break;

}

while (1)

{

cin>>t;

if (t=="#") break;

cout<<t;

if (check_equal(t)) cout<<" is correct"<<endl;

else check_similar(t);

}

return 0;

}

总结：今天两道题都是1A，没有什么好总结的

2021.1.18

1064：网线主管

题目大意：给出n个长度的管子，要求经过切割获得k个等长管子，求切割后最长管子长度

明显的二分，数据给出的是浮点数的，全部*100变成整数直接二分

#include<cstdio>
using namespace std;
#define N 10010
typedef long long LL;
int n,k;
double a[N],tmp[N];

bool check(int x)
{
	LL count=0;
	if (!x) return true;
	for (int i=1;i<=n;++i) count+=(LL)(tmp[i]/x);
	return count>=(LL)k;
}

int main()
{
	int l,r;
	scanf("%d%d",&n,&k),l=0,r=10000000;
	for (int i=1;i<=n;++i) scanf("%lf",&a[i]),tmp[i]=(int)(a[i]*100);
	while (l<=r)
	  {
	  	int mid=(l+r)>>1;
	  	if (check(mid)) l=mid+1;
	  	else r=mid-1;
	  }
	return printf("%.2lf",(l-1)*1.0/100),0;
}

#include<cstdio>

using namespace std;

#define N 10010

typedef long long LL;

int n,k;

double a[N],tmp[N];

bool check(int x)

{

LL count=0;

if (!x) return true;

for (int i=1;i<=n;++i) count+=(LL)(tmp[i]/x);

return count>=(LL)k;

}

int main()

{

int l,r;

scanf("%d%d",&n,&k),l=0,r=10000000;

for (int i=1;i<=n;++i) scanf("%lf",&a[i]),tmp[i]=(int)(a[i]*100);

while (l<=r)

{

int mid=(l+r)>>1;

if (check(mid)) l=mid+1;

else r=mid-1;

}

return printf("%.2lf",(l-1)*1.0/100),0;

}

总结：①一开始没看见等长，要认真读题②浮点数卡精度卡了一万年没有对，以后尽量避免卡精度③避免被0除，统计个数有可能超int

1088：滑雪

题目大意：就是那个经典的滑雪题

记忆化搜索，每次搜索起点的位置，途径更新dp值，下次搜索遇到直接返回dp值

#include<cstdio>
#include<algorithm>
using namespace std;
int r,c,a[110][110],dp[110][110],ans=0;
bool flag[110][110];

int dfs(int x,int y)
{
	int sum=0;
	if (flag[x][y]) return dp[x][y];
	flag[x][y]=true;
	if (x>1 && a[x][y]>a[x-1][y]) sum=max(sum,dfs(x-1,y)+1);
	if (y>1 && a[x][y]>a[x][y-1]) sum=max(sum,dfs(x,y-1)+1);
	if (x<r && a[x][y]>a[x+1][y]) sum=max(sum,dfs(x+1,y)+1);
	if (y<c && a[x][y]>a[x][y+1]) sum=max(sum,dfs(x,y+1)+1);
	return dp[x][y]=sum;
}

int main()
{
	scanf("%d%d",&r,&c);
	for (int i=1;i<=r;++i)
	  for (int j=1;j<=c;++j) scanf("%d",&a[i][j]);
	for (int i=1;i<=r;++i)
	  for (int j=1;j<=c;++j) ans=max(ans,dfs(i,j));
	return printf("%d",ans+1),0;
}

#include<cstdio>

#include<algorithm>

using namespace std;

int r,c,a[110][110],dp[110][110],ans=0;

bool flag[110][110];

int dfs(int x,int y)

{

int sum=0;

if (flag[x][y]) return dp[x][y];

flag[x][y]=true;

if (x>1 && a[x][y]>a[x-1][y]) sum=max(sum,dfs(x-1,y)+1);

if (y>1 && a[x][y]>a[x][y-1]) sum=max(sum,dfs(x,y-1)+1);

if (x<r && a[x][y]>a[x+1][y]) sum=max(sum,dfs(x+1,y)+1);

if (y<c && a[x][y]>a[x][y+1]) sum=max(sum,dfs(x,y+1)+1);

return dp[x][y]=sum;

}

int main()

{

scanf("%d%d",&r,&c);

for (int i=1;i<=r;++i)

for (int j=1;j<=c;++j) scanf("%d",&a[i][j]);

for (int i=1;i<=r;++i)

for (int j=1;j<=c;++j) ans=max(ans,dfs(i,j));

return printf("%d",ans+1),0;

}

2021.1.19

1251：丛林中的路

题目大意：MST裸题

多组数据MST，直接上并查集kruskal

#include<cstdio>
#include<algorithm>
using namespace std;
int n,father[30],tot,ans;
char s[3];
struct data
{
	int st,to,val;
}a[1010];

int find(int x)
{
	return x==father[x]?x:father[x]=find(father[x]);
}

void merge(int x,int y)
{
	int f1=find(x),f2=find(y);
	if (f1!=f2) father[f1]=f2;
}

bool cmp(data x,data y)
{
	return x.val<y.val;
}

int main()
{
	while (1)
	  {
	  	int k;
	  	scanf("%d",&n),tot=ans=0;
	  	for (int i=1;i<=26;++i) father[i]=i;
	  	if (!n) break;
	  	--n;
		while (n--)
		  {
		  	scanf("%s%d",s,&k);
		  	int x=s[0]-'A'+1,y;
		  	while (k--) scanf("%s%d",s,&y),a[++tot]=(data){x,s[0]-'A'+1,y};
		  }
		sort(a+1,a+tot+1,cmp);
		for (int i=1;i<=tot;++i)
		  if (find(a[i].st)!=find(a[i].to)) merge(a[i].st,a[i].to),ans+=a[i].val;
		printf("%d\n",ans);
	  }
	return 0;
}

#include<cstdio>

#include<algorithm>

using namespace std;

int n,father[30],tot,ans;

char s[3];

struct data

{

int st,to,val;

}a[1010];

int find(int x)

{

return x==father[x]?x:father[x]=find(father[x]);

}

void merge(int x,int y)

{

int f1=find(x),f2=find(y);

if (f1!=f2) father[f1]=f2;

}

bool cmp(data x,data y)

{

return x.val<y.val;

}

int main()

{

while (1)

{

int k;

scanf("%d",&n),tot=ans=0;

for (int i=1;i<=26;++i) father[i]=i;

if (!n) break;

--n;

while (n--)

{

scanf("%s%d",s,&k);

int x=s[0]-'A'+1,y;

while (k--) scanf("%s%d",s,&y),a[++tot]=(data){x,s[0]-'A'+1,y};

}

sort(a+1,a+tot+1,cmp);

for (int i=1;i<=tot;++i)

if (find(a[i].st)!=find(a[i].to)) merge(a[i].st,a[i].to),ans+=a[i].val;

printf("%d\n",ans);

}

return 0;

}

原本今天还做了NOI2001食物链，但是没有调出来，明日再更

2021.1.23

1833：排列

题目大意：求当前序列全排列按字典序排列的后k个

拿next_permutation水过

#include<cstdio>
#include<algorithm>
using namespace std;
#define N 1030
int T,n,k,a[N];
int main()
{
	scanf("%d",&T);
	while (T--)
	  {
	  	scanf("%d%d",&n,&k);
	  	for (int i=1;i<=n;++i) scanf("%d",&a[i]);
	  	for (int i=1;i<=k;++i) next_permutation(a+1,a+n+1);
	  	for (int i=1;i<=n;++i) printf("%d ",a[i]);
	  	printf("\n");
	  }
	return 0;
}

#include<cstdio>

#include<algorithm>

using namespace std;

#define N 1030

int T,n,k,a[N];

int main()

{

scanf("%d",&T);

while (T--)

{

scanf("%d%d",&n,&k);

for (int i=1;i<=n;++i) scanf("%d",&a[i]);

for (int i=1;i<=k;++i) next_permutation(a+1,a+n+1);

for (int i=1;i<=n;++i) printf("%d ",a[i]);

printf("\n");

}

return 0;

}

2021.1.25

2000：金币

题目大意：国王给金币，第一天给一个，接下来两天给两个，接下来三天给三个，输入某天，求第一天到该天金币数之和

假设输入为 $n$ ，判断 $\lfloor \sqrt{2n}\rfloor*\lfloor \sqrt{2n}+1\rfloor$ 与 $2n$ 的大小关系，预处理平方数前缀和即可

#include<cstdio>
#include<cmath>
using namespace std;
int n,sum[150];
int main()
{
	for (int i=1;i<=141;++i) sum[i]=i*i+sum[i-1];
	while (1)
	  {
	  	scanf("%d",&n);
	  	if (!n) break;
	  	int t=(int)sqrt(2*n);
	  	if (t*(t+1)==2*n) printf("%d %d\n",n,sum[t]);
	  	else if (t*(t+1)<2*n) printf("%d %d\n",n,sum[t]+(n-t*(t+1)/2)*(t+1));
	  	else printf("%d %d\n",n,sum[t]-(t*(t+1)/2-n)*t);
	  }
	return 0;
}

#include<cstdio>

#include<cmath>

using namespace std;

int n,sum[150];

int main()

{

for (int i=1;i<=141;++i) sum[i]=i*i+sum[i-1];

while (1)

{

scanf("%d",&n);

if (!n) break;

int t=(int)sqrt(2*n);

if (t*(t+1)==2*n) printf("%d %d\n",n,sum[t]);

else if (t*(t+1)<2*n) printf("%d %d\n",n,sum[t]+(n-t*(t+1)/2)*(t+1));

else printf("%d %d\n",n,sum[t]-(t*(t+1)/2-n)*t);

}

return 0;

}

2002：正方形

题目大意：给出多个二维整数坐标，求这些点最多能构成多少个正方形

第一眼枚举对角线，用map判断另两点坐标，但是几何数学不好没求出另两点坐标公式~~（高中数学全还给老师了）~~，看了题解发现还不是高中数学，是初中数学，具体看https://www.luogu.com.cn/problem/solution/P1665，枚举对角线 $O(n^2)$ ，求中点坐标可能是浮点数，所以输入统一成浮点数了，又怕map产生浮点数精度误差，把判断改成二分了，总时间复杂度 $O(T(nlogn+n^2logn))$ ，最后答案除以2

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define eps 1e-6
int n,ans;
struct data
{
	double X,Y;
}a[1010];

bool cmp(data x,data y)
{
	return fabs(x.X-y.X)<eps?x.Y<y.Y:x.X<y.X;
}

bool check(double x,double y)
{
	int l=1,r=n;
	while (l<=r)
	  {
	  	int mid=(l+r)>>1;
	  	if (fabs(a[mid].X-x)<eps && fabs(a[mid].Y-y)<eps) return true;
		else if (a[mid].X<x || fabs(a[mid].X-x)<eps && a[mid].Y<y) l=mid+1;
		else r=mid-1;  
	  }
	return false;
}

int main()
{
	while (1)
	  {
	  	scanf("%d",&n),ans=0;
	  	if (!n) break;
		for (int i=1;i<=n;++i) scanf("%lf%lf",&a[i].X,&a[i].Y);
		sort(a+1,a+n+1,cmp);
		for (int i=1;i<n;++i)
		  for (int j=i+1;j<=n;++j)
		    {
		    	double midx=(a[i].X+a[j].X)/2,midy=(a[i].Y+a[j].Y)/2;
		    	if (check(midx-midy+a[i].Y,midy+midx-a[i].X) && check(midx+midy-a[i].Y,midy-midx+a[i].X)) ++ans;
			}
		printf("%d\n",ans/2);
	  }
	return 0; 
}

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

#define eps 1e-6

int n,ans;

struct data

{

double X,Y;

}a[1010];

bool cmp(data x,data y)

{

return fabs(x.X-y.X)<eps?x.Y<y.Y:x.X<y.X;

}

bool check(double x,double y)

{

int l=1,r=n;

while (l<=r)

{

int mid=(l+r)>>1;

if (fabs(a[mid].X-x)<eps && fabs(a[mid].Y-y)<eps) return true;

else if (a[mid].X<x || fabs(a[mid].X-x)<eps && a[mid].Y<y) l=mid+1;

else r=mid-1;

}

return false;

}

int main()

{

while (1)

{

scanf("%d",&n),ans=0;

if (!n) break;

for (int i=1;i<=n;++i) scanf("%lf%lf",&a[i].X,&a[i].Y);

sort(a+1,a+n+1,cmp);

for (int i=1;i<n;++i)

for (int j=i+1;j<=n;++j)

{

double midx=(a[i].X+a[j].X)/2,midy=(a[i].Y+a[j].Y)/2;

if (check(midx-midy+a[i].Y,midy+midx-a[i].X) && check(midx+midy-a[i].Y,midy-midx+a[i].X)) ++ans;

}

printf("%d\n",ans/2);

}

return 0;

}

总结：①多耐下心推导

2021.1.26

2039：反反复复

题目大意：给出按行排列的字符矩阵的字符串形式，求按列排列的字符串

按照题意模拟即可

#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int n;
char s[210][21],t[210];
int main()
{
	scanf("%d%s",&n,t+1);
	for (int i=1;i<=strlen(t+1);++i)
	  if ((int)(ceil(i*1.0/n))&1) 
	  	if (i%n==0) s[i/n][n]=t[i];
	  	else s[(int)ceil(i*1.0/n)][i%n]=t[i];
	  else 
	    if (i%n==0) s[i/n][1]=t[i];
	    else s[(int)ceil(i*1.0/n)][n-i%n+1]=t[i];
	for (int i=1;i<=n;++i)
	  for (int j=1;j<=strlen(t+1)/n;++j) printf("%c",s[j][i]);
	return 0;
}

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

int n;

char s[210][21],t[210];

int main()

{

scanf("%d%s",&n,t+1);

for (int i=1;i<=strlen(t+1);++i)

if ((int)(ceil(i*1.0/n))&1)

if (i%n==0) s[i/n][n]=t[i];

else s[(int)ceil(i*1.0/n)][i%n]=t[i];

else

if (i%n==0) s[i/n][1]=t[i];

else s[(int)ceil(i*1.0/n)][n-i%n+1]=t[i];

for (int i=1;i<=n;++i)

for (int j=1;j<=strlen(t+1)/n;++j) printf("%c",s[j][i]);

return 0;

}

2121：英语数字转换器

题目大意：给出整数的英文描述，保证英文描述从高位开始描述，输出该整数

多组数据整行读入需要以空格作为分隔符分割字符串，将单词提取出来，没有Python的split函数，从网上搜到了C语言string.h头文件的strtok函数，可以将char*中的单词以任意分隔符分割，对应C++中的cstring头文件，分割出来之后将对应的hundred、thousand和million提取出来，需要进行一个判断，是否需要对当前的数进行相乘，前面的数需要乘，后面的数需要加，特判一下即可

#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
using namespace std;
string s;

int get(string t)
{
	if (t=="zero") return 0;
	if (t=="one") return 1;
	if (t=="two") return 2;
	if (t=="three") return 3;
	if (t=="four") return 4;
	if (t=="five") return 5;
	if (t=="six") return 6;
	if (t=="seven") return 7;
	if (t=="eight") return 8;
	if (t=="nine") return 9;
	if (t=="ten") return 10;
	if (t=="eleven") return 11;
	if (t=="twelve") return 12;
	if (t=="thirteen") return 13;
	if (t=="fourteen") return 14;
	if (t=="fifteen") return 15;
	if (t=="sixteen") return 16;
	if (t=="seventeen") return 17;
	if (t=="eighteen") return 18;
	if (t=="nineteen") return 19;
	if (t=="twenty") return 20;
	if (t=="thirty") return 30;
	if (t=="forty") return 40;
	if (t=="fifty") return 50;
	if (t=="sixty") return 60;
	if (t=="seventy") return 70;
	if (t=="eighty") return 80;
	if (t=="ninety") return 90;
}

int main()
{
	while (getline(cin,s))
	  {
	  	if (s=="") break;
	  	char t[210];
	    strcpy(t,s.c_str());
	  	char *token=strtok(t," ");
	  	int num=0;
	  	while (token!=NULL) 
	  	  {
	  	  	string tmp="";
	  	  	for (int i=0;i<strlen(token);++i) tmp+=token[i];
	  	  	if (tmp=="negative") printf("-");
	  	  	else if (tmp!="hundred" && tmp!="thousand" && tmp!="million") num+=get(tmp);
	  	  	else 
	  	  	  {
	  	  	  	if (tmp=="hundred")
	  	  	  	  if (num>100) 
	  	  	  	    {
	  	  	  	    	int temp=num%100;
	  	  	  	    	num+=temp*100-temp;
					}
	  	  	  	  else num*=100;
	  	  	  	if (tmp=="thousand")
	  	  	  	  if (num>1000) 
	  	  	  	    {
	  	  	  	    	int temp=num%1000;
	  	  	  	    	num+=temp*1000-temp;
				    }
	  	  	  	  else num*=1000;
	  	  	  	if (tmp=="million") num*=1000000;
			  }
	  	  	token=strtok(NULL," ");
		  }
		printf("%d\n",num);
	  }
	return 0;
}

#include<cstdio>

#include<cstring>

#include<string>

#include<iostream>

using namespace std;

string s;

int get(string t)

{

if (t=="zero") return 0;

if (t=="one") return 1;

if (t=="two") return 2;

if (t=="three") return 3;

if (t=="four") return 4;

if (t=="five") return 5;

if (t=="six") return 6;

if (t=="seven") return 7;

if (t=="eight") return 8;

if (t=="nine") return 9;

if (t=="ten") return 10;

if (t=="eleven") return 11;

if (t=="twelve") return 12;

if (t=="thirteen") return 13;

if (t=="fourteen") return 14;

if (t=="fifteen") return 15;

if (t=="sixteen") return 16;

if (t=="seventeen") return 17;

if (t=="eighteen") return 18;

if (t=="nineteen") return 19;

if (t=="twenty") return 20;

if (t=="thirty") return 30;

if (t=="forty") return 40;

if (t=="fifty") return 50;

if (t=="sixty") return 60;

if (t=="seventy") return 70;

if (t=="eighty") return 80;

if (t=="ninety") return 90;

}

int main()

{

while (getline(cin,s))

{

if (s=="") break;

char t[210];

strcpy(t,s.c_str());

char *token=strtok(t," ");

int num=0;

while (token!=NULL)

{

string tmp="";

for (int i=0;i<strlen(token);++i) tmp+=token[i];

if (tmp=="negative") printf("-");

else if (tmp!="hundred" && tmp!="thousand" && tmp!="million") num+=get(tmp);

else

{

if (tmp=="hundred")

if (num>100)

{

int temp=num%100;

num+=temp*100-temp;

}

else num*=100;

if (tmp=="thousand")

if (num>1000)

{

int temp=num%1000;

num+=temp*1000-temp;

}

else num*=1000;

if (tmp=="million") num*=1000000;

}

token=strtok(NULL," ");

}

printf("%d\n",num);

}

return 0;

}

总结：①strtok使用char*可能内存不足，改为使用char[]

2021.1.27

2339：矩阵剪刀石头布

题目大意：矩阵上标着剪刀石头布，每天矩阵上所有点对上下左右相邻的点进行PK，获胜的一方将失败的一方格子占据，求n天后的矩阵

直接模拟，另开一个字符数组存储当天PK后的矩阵形态，防止后面的点判断时相互影响

#include<cstdio>
using namespace std;
int n,m,day;
char s[110][110],a[110][110];

bool judge(int x,int y,char t)
{
	if (t=='R')
	  if (s[x-1][y]=='P' || s[x+1][y]=='P' || s[x][y+1]=='P' || s[x][y-1]=='P') return true;
	  else return false;
	if (t=='S')
	  if (s[x-1][y]=='R' || s[x+1][y]=='R' || s[x][y+1]=='R' || s[x][y-1]=='R') return true;
	  else return false;
	if (t=='P')
	  if (s[x-1][y]=='S' || s[x+1][y]=='S' || s[x][y+1]=='S' || s[x][y-1]=='S') return true;
	  else return false;
}

int main()
{
	scanf("%d%d%d",&n,&m,&day);
	for (int i=1;i<=n;++i) scanf("%s",s[i]+1);
	while (day--)
	  {
	  	for (int i=1;i<=n;++i)
	  	  for (int j=1;j<=m;++j)
	  	    if (s[i][j]=='R')
			  if (judge(i,j,'R')) a[i][j]='P';
			  else a[i][j]='R';
			else if (s[i][j]=='S')
			  if (judge(i,j,'S')) a[i][j]='R';
			  else a[i][j]='S';
			else 
			  if (judge(i,j,'P')) a[i][j]='S';
			  else a[i][j]='P';
		for (int i=1;i<=n;++i)
		  for (int j=1;j<=m;++j) s[i][j]=a[i][j];
	  }
	for (int i=1;i<=n;++i)
	  {
	  	for (int j=1;j<=m;++j) printf("%c",s[i][j]);
	  	printf("\n");
	  }
	return 0;
}

#include<cstdio>

using namespace std;

int n,m,day;

char s[110][110],a[110][110];

bool judge(int x,int y,char t)

{

if (t=='R')

if (s[x-1][y]=='P' || s[x+1][y]=='P' || s[x][y+1]=='P' || s[x][y-1]=='P') return true;

else return false;

if (t=='S')

if (s[x-1][y]=='R' || s[x+1][y]=='R' || s[x][y+1]=='R' || s[x][y-1]=='R') return true;

else return false;

if (t=='P')

if (s[x-1][y]=='S' || s[x+1][y]=='S' || s[x][y+1]=='S' || s[x][y-1]=='S') return true;

else return false;

}

int main()

{

scanf("%d%d%d",&n,&m,&day);

for (int i=1;i<=n;++i) scanf("%s",s[i]+1);

while (day--)

{

for (int i=1;i<=n;++i)

for (int j=1;j<=m;++j)

if (s[i][j]=='R')

if (judge(i,j,'R')) a[i][j]='P';

else a[i][j]='R';

else if (s[i][j]=='S')

if (judge(i,j,'S')) a[i][j]='R';

else a[i][j]='S';

else

if (judge(i,j,'P')) a[i][j]='S';

else a[i][j]='P';

for (int i=1;i<=n;++i)

for (int j=1;j<=m;++j) s[i][j]=a[i][j];

}

for (int i=1;i<=n;++i)

{

for (int j=1;j<=m;++j) printf("%c",s[i][j]);

printf("\n");

}

return 0;

}

2388：寻找中位数

题目大意：题目就是题意

n最大是10000，懒得想 $O(n)$ 做法了，直接排序取n/2+1

#include<cstdio>
#include<algorithm>
using namespace std;
int n,a[10010];
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;++i) scanf("%d",&a[i]);
	return sort(a+1,a+n+1),printf("%d",a[n/2+1]),0;
}

#include<cstdio>

#include<algorithm>

using namespace std;

int n,a[10010];

int main()

{

scanf("%d",&n);

for (int i=1;i<=n;++i) scanf("%d",&a[i]);

return sort(a+1,a+n+1),printf("%d",a[n/2+1]),0;

}

2390：银行利息

题目大意：给出年利率、本金和存款年数，求最终钱数的整数部分

最终不要四舍五入，直接强制类型转换取整，另外可能会爆int，所以强制转换为long long

#include<cstdio>
#include<iostream>
using namespace std;
int r,m,y;
double ans;
int main()
{
	scanf("%d%d%d",&r,&m,&y),ans=m;
	while (y--) ans=ans*(1+r*1.0/100);
	return cout<<(long long)ans<<endl,0;
}

#include<cstdio>

#include<iostream>

using namespace std;

int r,m,y;

double ans;

int main()

{

scanf("%d%d%d",&r,&m,&y),ans=m;

while (y--) ans=ans*(1+r*1.0/100);

return cout<<(long long)ans<<endl,0;

}

2021.1.28

2524：宗教信仰

题目大意：给出两两连接关系，求最多有多少个互不连通的子集

裸并查集

#include<cstdio>
using namespace std;
#define N 50010
int n,m,father[N],T,ans;

int find(int x)
{
	return x==father[x]?x:father[x]=find(father[x]);
}

void merge(int x,int y)
{
	int f1=find(x),f2=find(y);
	if (f1!=f2) father[f1]=f2;
}

int main()
{
	int x,y;
	while (1)
	  {
	  	scanf("%d%d",&n,&m),++T,ans=0;
	  	if (!n && !m) break;
	  	for (int i=1;i<=n;++i) father[i]=i;
	  	for (int i=1;i<=m;++i) scanf("%d%d",&x,&y),merge(x,y);
	  	for (int i=1;i<=n;++i)
	  	  if (find(i)==i) ++ans;
	  	printf("Case %d: %d\n",T,ans);
	  }
	return 0;
}

#include<cstdio>

using namespace std;

#define N 50010

int n,m,father[N],T,ans;

int find(int x)

{

return x==father[x]?x:father[x]=find(father[x]);

}

void merge(int x,int y)

{

int f1=find(x),f2=find(y);

if (f1!=f2) father[f1]=f2;

}

int main()

{

int x,y;

while (1)

{

scanf("%d%d",&n,&m),++T,ans=0;

if (!n && !m) break;

for (int i=1;i<=n;++i) father[i]=i;

for (int i=1;i<=m;++i) scanf("%d%d",&x,&y),merge(x,y);

for (int i=1;i<=n;++i)

if (find(i)==i) ++ans;

printf("Case %d: %d\n",T,ans);

}

return 0;

}

2675：计算书费

题目大意：给出价格数量求累加和

不多说了小学生都会

#include<cstdio>
using namespace std;
int T,a[10];
double price[10]={28.9,32.7,45.6,78,35,86.2,27.8,43,56,65};
int main()
{
	scanf("%d",&T);
	while (T--)
	  {
	  	double ans=0;
	  	for (int i=0;i<10;++i) scanf("%d",&a[i]),ans+=a[i]*price[i];
	  	printf("%.2lf\n",ans);
	  }
	return 0;
}

#include<cstdio>

using namespace std;

int T,a[10];

double price[10]={28.9,32.7,45.6,78,35,86.2,27.8,43,56,65};

int main()

{

scanf("%d",&T);

while (T--)

{

double ans=0;

for (int i=0;i<10;++i) scanf("%d",&a[i]),ans+=a[i]*price[i];

printf("%.2lf\n",ans);

}

return 0;

}

3251：最少费用

题目大意：给出费用矩阵，从左上角走到右下角最小费用

题意可能一上来会被唬住，因为可以上下左右四个方向走，那么就和普通dp不太一样，但是题目中说明矩阵的费用从左到右从上到下升序排列，所以只有往右和往下走是最优方案，再折回上和左只会徒增费用，所以这一条件将题目转换为了普通dp，转移方程 $dp[i][j]=min(dp[i-1][j],dp[i][j-1])+a[i][j]$ ，另外注意处理一下边界

#include<cstdio>
#include<algorithm>
using namespace std;
#define N 110
#define inf 0x7fffffff
int n,a[N][N],dp[N][N];
int main()
{
	scanf("%d",&n);
	for (int i=0;i<N;++i)
	  for (int j=0;j<N;++j) dp[i][j]=inf; 
	for (int i=1;i<=n;++i)
	  for (int j=1;j<=n;++j) scanf("%d",&a[i][j]);
	dp[1][1]=a[1][1];
	for (int i=1;i<=n;++i)
	  for (int j=1;j<=n;++j)
	    if (i==1 && j==1) continue;
	    else dp[i][j]=min(dp[i-1][j],dp[i][j-1])+a[i][j];
	return printf("%d",dp[n][n]),0;
}

#include<cstdio>

#include<algorithm>

using namespace std;

#define N 110

#define inf 0x7fffffff

int n,a[N][N],dp[N][N];

int main()

{

scanf("%d",&n);

for (int i=0;i<N;++i)

for (int j=0;j<N;++j) dp[i][j]=inf;

for (int i=1;i<=n;++i)

for (int j=1;j<=n;++j) scanf("%d",&a[i][j]);

dp[1][1]=a[1][1];

for (int i=1;i<=n;++i)

for (int j=1;j<=n;++j)

if (i==1 && j==1) continue;

else dp[i][j]=min(dp[i-1][j],dp[i][j-1])+a[i][j];

return printf("%d",dp[n][n]),0;

}

2021.1.29

2676：整数的个数

题目大意：给出n个数，求1，5，10出现的次数

#include<cstdio>
using namespace std;
int n,a[110],c1,c2,c3;
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;++i) 
	  {
	  	scanf("%d",&a[i]);
	  	if (a[i]==1) ++c1;
	  	if (a[i]==5) ++c2;
	  	if (a[i]==10) ++c3;
	  }
	return printf("%d\n%d\n%d",c1,c2,c3),0;
}

#include<cstdio>

using namespace std;

int n,a[110],c1,c2,c3;

int main()

{

scanf("%d",&n);

for (int i=1;i<=n;++i)

{

scanf("%d",&a[i]);

if (a[i]==1) ++c1;

if (a[i]==5) ++c2;

if (a[i]==10) ++c3;

}

return printf("%d\n%d\n%d",c1,c2,c3),0;

}

3752：走迷宫

题目大意：给出迷宫求左上角走到右下角经过的最少空格个数，保证一定有解

bfs可以直接做，但一看数据范围只有40，直接连边dijkstra

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
#define pa pair<int,int>
#define inf 0x7fffffff
int n,m,cnt,h[1700],dis[1700];
struct data
{
	int to,next,v;
}edge[1700<<2];
char s[50][50];

int get(int x,int y)
{
	return (x-1)*m+y;
}

void add(int u,int v,int w)
{
	edge[++cnt]=(data){v,h[u],w},h[u]=cnt,edge[++cnt]=(data){u,h[v],w},h[v]=cnt;
}

void dijkstra()
{
	priority_queue<pa,vector<pa>,greater<pa> >q;
	for (int i=1;i<=get(n,m);++i) dis[i]=inf;
	dis[1]=0,q.push(make_pair(0,1));
	while (!q.empty())
	  {
	  	int now=q.top().second;
	  	q.pop();
	  	for (int i=h[now];i;i=edge[i].next)
	  	  if (dis[now]+edge[i].v<dis[edge[i].to])
	  	    dis[edge[i].to]=dis[now]+edge[i].v,q.push(make_pair(dis[edge[i].to],edge[i].to));
	  }
}

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;++i) scanf("%s",s[i]+1);
	for (int i=1;i<=n;++i)
	  for (int j=1;j<=m;++j)
	    if (s[i][j]=='.') 
	      {
	      	if (s[i-1][j]=='.') add(get(i,j),get(i-1,j),1);
	      	if (s[i+1][j]=='.') add(get(i,j),get(i+1,j),1);
	      	if (s[i][j-1]=='.') add(get(i,j),get(i,j-1),1);
	      	if (s[i][j+1]=='.') add(get(i,j),get(i,j+1),1);
		  }
	return dijkstra(),printf("%d",dis[get(n,m)]+1),0;
}

#include<cstdio>

#include<vector>

#include<queue>

using namespace std;

#define pa pair<int,int>

#define inf 0x7fffffff

int n,m,cnt,h[1700],dis[1700];

struct data

{

int to,next,v;

}edge[1700<<2];

char s[50][50];

int get(int x,int y)

{

return (x-1)*m+y;

}

void add(int u,int v,int w)

{

edge[++cnt]=(data){v,h[u],w},h[u]=cnt,edge[++cnt]=(data){u,h[v],w},h[v]=cnt;

}

void dijkstra()

{

priority_queue<pa,vector<pa>,greater<pa> >q;

for (int i=1;i<=get(n,m);++i) dis[i]=inf;

dis[1]=0,q.push(make_pair(0,1));

while (!q.empty())

{

int now=q.top().second;

q.pop();

for (int i=h[now];i;i=edge[i].next)

if (dis[now]+edge[i].v<dis[edge[i].to])

dis[edge[i].to]=dis[now]+edge[i].v,q.push(make_pair(dis[edge[i].to],edge[i].to));

}

int main()

{

scanf("%d%d",&n,&m);

for (int i=1;i<=n;++i) scanf("%s",s[i]+1);

for (int i=1;i<=n;++i)

for (int j=1;j<=m;++j)

if (s[i][j]=='.')

{

if (s[i-1][j]=='.') add(get(i,j),get(i-1,j),1);

if (s[i+1][j]=='.') add(get(i,j),get(i+1,j),1);

if (s[i][j-1]=='.') add(get(i,j),get(i,j-1),1);

if (s[i][j+1]=='.') add(get(i,j),get(i,j+1),1);

}

return dijkstra(),printf("%d",dis[get(n,m)]+1),0;

}

2021.1.30

3244：跳水比赛

题目大意：一通逻辑推理

应该正解是dfs那种，直接暴搜，然后边搜边判断，不符合条件直接回溯，但是因为条件少，我直接手玩了

#include<iostream>
using namespace std;
int main()
{
    cout<<3<<" "<<1<<" "<<5<<" "<<2<<" "<<4<<endl;
    return 0;
}

#include<iostream>

using namespace std;

int main()

{

cout<<3<<" "<<1<<" "<<5<<" "<<2<<" "<<4<<endl;

return 0;

}

3246：展览会

题目大意：给出一坨区间，判断区间重合最多的区间个数

正解应该是有 $O(nlogn)$ 的做法，但是数据范围太小我直接 $n^2$ 暴力了

#include<cstdio>
#include<algorithm>
using namespace std;
int n,x[2010],y[2010],ans;
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;++i) scanf("%d",&x[i]);
	for (int i=1;i<=n;++i) scanf("%d",&y[i]);
	for (int i=1;i<=2000;++i) 
	  {
	  	int sum=0;
	  	for (int j=1;j<=n;++j)
	  	  if (x[j]<=i && i<y[j]) ++sum;
	  	ans=max(ans,sum);
	  }
	return printf("%d",ans),0;
}

#include<cstdio>

#include<algorithm>

using namespace std;

int n,x[2010],y[2010],ans;

int main()

{

scanf("%d",&n);

for (int i=1;i<=n;++i) scanf("%d",&x[i]);

for (int i=1;i<=n;++i) scanf("%d",&y[i]);

for (int i=1;i<=2000;++i)

{

int sum=0;

for (int j=1;j<=n;++j)

if (x[j]<=i && i<y[j]) ++sum;

ans=max(ans,sum);

}

return printf("%d",ans),0;

}

2021.1.30 22:35 UPD：直接打暴力也太混了，不学一下 $O(nlogn)$ 做法么，自然是要学的

把每个区间想象成滑块，从区间最左端滑到最右端，这个动态的过程可以理解为遇到左端点答案+1，遇到右端点答案-1，于是我们排一下序 $O(n)$ 扫一遍，边扫边记录最大值即可，时间复杂度 $O(nlogn)$ .

#include<cstdio>
#include<algorithm>
using namespace std;
#define N 1010
int n,Count,ans;
struct data
{
	int val;
	bool mark;
}a[N<<1];

bool cmp(data x,data y)
{
	return x.val==y.val?x.mark>y.mark:x.val<y.val;
}

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;++i) scanf("%d",&a[i].val),a[i].mark=true;
	for (int i=1;i<=n;++i) scanf("%d",&a[i+n].val),--a[i+n].val,a[i+n].mark=false;
	sort(a+1,a+2*n+1,cmp);
	for (int i=1;i<=2*n;++i) 
	  if (a[i].mark) ++Count,ans=max(ans,Count);
	  else --Count,ans=max(ans,Count);
	return printf("%d",ans),0;
}

#include<cstdio>

#include<algorithm>

using namespace std;

#define N 1010

int n,Count,ans;

struct data

{

int val;

bool mark;

}a[N<<1];

bool cmp(data x,data y)

{

return x.val==y.val?x.mark>y.mark:x.val<y.val;

}

int main()

{

scanf("%d",&n);

for (int i=1;i<=n;++i) scanf("%d",&a[i].val),a[i].mark=true;

for (int i=1;i<=n;++i) scanf("%d",&a[i+n].val),--a[i+n].val,a[i+n].mark=false;

sort(a+1,a+2*n+1,cmp);

for (int i=1;i<=2*n;++i)

if (a[i].mark) ++Count,ans=max(ans,Count);

else --Count,ans=max(ans,Count);

return printf("%d",ans),0;

}

3179：最长单词

题目大意：给出一个句子，求句子中最长单词是什么，若有长度相同的求最后出现的单词

又是分割字符串，直接默写

#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
string s;
int main()
{
	while (getline(cin,s))
	  {
	  	int len=0;
	  	char t[210],ans[210];
	  	strcpy(t,s.c_str());
	  	char *token=strtok(t," ,.");
	  	while (token!=NULL)
	  	  {
	  	  	if (strlen(token)>=len) len=strlen(token),strcpy(ans,token);
	  	  	token=strtok(NULL," ,.");
		  }
		cout<<ans<<endl;
	  }
	return 0;
}

#include<cstdio>

#include<iostream>

#include<string>

#include<cstring>

using namespace std;

string s;

int main()

{

while (getline(cin,s))

{

int len=0;

char t[210],ans[210];

strcpy(t,s.c_str());

char *token=strtok(t," ,.");

while (token!=NULL)

{

if (strlen(token)>=len) len=strlen(token),strcpy(ans,token);

token=strtok(NULL," ,.");

}

cout<<ans<<endl;

}

return 0;

}

2021.1.31

2777：人

题目大意：给出一段C++面向对象代码，代码填空

没啥太难的，读明白了就行了，里面都有注释，不过知道了类内private成员函数在类外也可以被访问，并不是完全不能访问，回头复习的时候再深入研究一下这个问题

#include<iostream>
using namespace std;
int main()
{
    cout<<"float"<<endl<<"figureQuota"<<endl;
    return 0;
}

#include<iostream>

using namespace std;

int main()

{

cout<<"float"<<endl<<"figureQuota"<<endl;

return 0;

}

3252：最大正向匹配

题目大意：给出两个字符串，再给出一个模式串，求以这两个字符串为前缀和后缀的模式串子串的最大长度

贪心，前缀正着循环，后缀倒着循环，找到的第一个符合的即为最长，因为保证存在解，所以不需要判断前缀和后缀的位置问题

#include<string>
#include<iostream>
using namespace std;
string s1,s2,s;
int n;
int main()
{
	cin>>s1>>s2>>n;
	while (n--) 
	  {
	  	cin>>s;
	  	int p1,p2;
	  	for (int i=0;i<s.length()-s1.length()+1;++i) 
	  	  if (s.substr(i,s1.length())==s1)
			{
				p1=i;
				break;
			}
		for (int i=s.length()-s2.length();i>=0;--i)
		  if (s.substr(i,s2.length())==s2)
		    {
		    	p2=i+s2.length()-1;
		    	break;
			}
		cout<<s.substr(p1,p2-p1+1)<<endl;
	  }
	return 0;
}

#include<string>

#include<iostream>

using namespace std;

string s1,s2,s;

int n;

int main()

{

cin>>s1>>s2>>n;

while (n--)

{

cin>>s;

int p1,p2;

for (int i=0;i<s.length()-s1.length()+1;++i)

if (s.substr(i,s1.length())==s1)

{

p1=i;

break;

}

for (int i=s.length()-s2.length();i>=0;--i)

if (s.substr(i,s2.length())==s2)

{

p2=i+s2.length()-1;

break;

}

cout<<s.substr(p1,p2-p1+1)<<endl;

}

return 0;

}

3262：新数字三角形

题目大意：在原数字三角形的基础上，改为给出初始位置，求在当前位置所能走的所有路径中的数值最大值

还是和原数字三角形做法差不多，倒序dp，只不过转移方程相加改为取max

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,a[110][110],dp[110][110];
int main()
{
	while (1)
	  {
	  	int r,c;
	  	scanf("%d",&n),memset(dp,0,sizeof(dp));
	  	if (!n) break; 
	  	for (int i=1;i<=n;++i)
	  	  for (int j=1;j<=i;++j) scanf("%d",&a[i][j]);
	  	scanf("%d%d",&r,&c);
	  	for (int i=1;i<=n;++i) dp[n][i]=a[n][i];
	  	for (int i=n-1;i;--i)
		  for (int j=1;j<=i;++j) dp[i][j]=max(dp[i+1][j],max(dp[i+1][j+1],a[i][j]));
		printf("%d\n",dp[r][c]);
	  }
	return 0;
}

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

int n,a[110][110],dp[110][110];

int main()

{

while (1)

{

int r,c;

scanf("%d",&n),memset(dp,0,sizeof(dp));

if (!n) break;

for (int i=1;i<=n;++i)

for (int j=1;j<=i;++j) scanf("%d",&a[i][j]);

scanf("%d%d",&r,&c);

for (int i=1;i<=n;++i) dp[n][i]=a[n][i];

for (int i=n-1;i;--i)

for (int j=1;j<=i;++j) dp[i][j]=max(dp[i+1][j],max(dp[i+1][j+1],a[i][j]));

printf("%d\n",dp[r][c]);

}

return 0;

}

2021.2.1

1847：Tram

题目大意：给出一张有向图，再给出每个结点所连的m条边，第一条边权值为0，其余边权值为1，求指定初始和结束结点之间的最短路

本不想做英文题面的题，但是发现这是2018年北大信科夏令营机试真题，就做了一下，其实重点在于读题，我第一遍读没读懂，后来配合着百度翻译搞懂了，英文水平还需要提升，然后翻译过来基本上不用怎么分析就是题目大意那个样子，因为没有负权边，直接上dijkstra秒过

#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
#define N 110
#define inf 0x7fffffff
#define pa pair<int,int>
int n,a,b,m,cnt,h[N],dis[N];
struct data
{
	int to,next,v;
}edge[N<<2];

void add(int u,int v,int w)
{
	edge[++cnt]=(data){v,h[u],w},h[u]=cnt;
}

void dijkstra(int S)
{
	priority_queue<pa,vector<pa>,greater<pa> >q;
	for (int i=1;i<=n;++i) dis[i]=inf;
	dis[S]=0,q.push(make_pair(0,S));
	while (!q.empty())
	  {
	  	int now=q.top().second;
		q.pop();
		for (int i=h[now];i;i=edge[i].next)
		  if (dis[edge[i].to]>dis[now]+edge[i].v)
		    dis[edge[i].to]=dis[now]+edge[i].v,q.push(make_pair(dis[edge[i].to],edge[i].to));
	  }
}

int main()
{
	int x;
	scanf("%d%d%d",&n,&a,&b);
	for (int i=1;i<=n;++i)
	  {
	  	scanf("%d",&m);
	  	if (!m) continue;
	  	scanf("%d",&x),--m,add(i,x,0);
	  	while (m--) scanf("%d",&x),add(i,x,1);
	  }
	return dijkstra(a),printf("%d",dis[b]==inf?-1:dis[b]),0;
}

#include<cstdio>

#include<vector>

#include<queue>

using namespace std;

#define N 110

#define inf 0x7fffffff

#define pa pair<int,int>

int n,a,b,m,cnt,h[N],dis[N];

struct data

{

int to,next,v;

}edge[N<<2];

void add(int u,int v,int w)

{

edge[++cnt]=(data){v,h[u],w},h[u]=cnt;

}

void dijkstra(int S)

{

priority_queue<pa,vector<pa>,greater<pa> >q;

for (int i=1;i<=n;++i) dis[i]=inf;

dis[S]=0,q.push(make_pair(0,S));

while (!q.empty())

{

int now=q.top().second;

q.pop();

for (int i=h[now];i;i=edge[i].next)

if (dis[edge[i].to]>dis[now]+edge[i].v)

dis[edge[i].to]=dis[now]+edge[i].v,q.push(make_pair(dis[edge[i].to],edge[i].to));

}

int main()

{

int x;

scanf("%d%d%d",&n,&a,&b);

for (int i=1;i<=n;++i)

{

scanf("%d",&m);

if (!m) continue;

scanf("%d",&x),--m,add(i,x,0);

while (m--) scanf("%d",&x),add(i,x,1);

}

return dijkstra(a),printf("%d",dis[b]==inf?-1:dis[b]),0;

}

3406：书架

题目大意：给出n个奶牛高度和书架高度，求最少多少个奶牛叠罗汉比书架高

贪心+排序

#include<cstdio>
#include<algorithm>
using namespace std;
#define N 20010
int n,b,a[N];

bool cmp(int x,int y)
{
	return x>y;
}

int main()
{
	scanf("%d%d",&n,&b);
	for (int i=1;i<=n;++i) scanf("%d",&a[i]);
	sort(a+1,a+n+1,cmp);
	for (int i=1;i<=n;++i)
	  if (b>0) b-=a[i];
	  else 
	    {
	    	printf("%d",--i);
	    	break;
		}
	return 0;
}

#include<cstdio>

#include<algorithm>

using namespace std;

#define N 20010

int n,b,a[N];

bool cmp(int x,int y)

{

return x>y;

}

int main()

{

scanf("%d%d",&n,&b);

for (int i=1;i<=n;++i) scanf("%d",&a[i]);

sort(a+1,a+n+1,cmp);

for (int i=1;i<=n;++i)

if (b>0) b-=a[i];

else

{

printf("%d",--i);

break;

}

return 0;

}

2021.2.2

3390：最好的草

题目大意：给出一个字符矩阵，#表示草地，规定相连的草地面积为1或者2为最好的草地，求最好草地个数

比较简单的bfs，开一个二维数组记录草地的遍历情况，然后将相邻的草地都入队列，然后队列中判断边判断边入队列，最后返回队列长度判断是否为1或者2就OK了

#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int n,m,ans,q[1100],head,tail;
char s[110][110];
bool flag[110][110];

int get(int x,int y)
{
	return (x-1)*m+y;
}

int bfs(int x,int y)
{
	flag[x][y]=true;
	if (!head && !tail) q[++head]=get(x,y),++tail;
	while (head<=tail)
	  {
	  	int X=ceil(q[head]*1.0/m),Y=q[head]%m;
	  	if (!Y) Y=m;
	  	flag[X][Y]=true;
	  	if (s[X-1][Y]=='#' && !flag[X-1][Y]) q[++tail]=get(X-1,Y);
	  	if (s[X+1][Y]=='#' && !flag[X+1][Y]) q[++tail]=get(X+1,Y);
	  	if (s[X][Y-1]=='#' && !flag[X][Y-1]) q[++tail]=get(X,Y-1);
	  	if (s[X][Y+1]=='#' && !flag[X][Y+1]) q[++tail]=get(X,Y+1);
	  	++head;
	  }
	return tail;
}

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;++i) scanf("%s",s[i]+1);
	for (int i=1;i<=n;++i)
	  for (int j=1;j<=m;++j)
	    if (s[i][j]=='#' && !flag[i][j])
		  {
		  	memset(q,0,sizeof(q)),head=tail=0;
		  	int t=bfs(i,j);
		  	if (t==1 || t==2) ++ans;
		  } 
	return printf("%d",ans),0;
}

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

int n,m,ans,q[1100],head,tail;

char s[110][110];

bool flag[110][110];

int get(int x,int y)

{

return (x-1)*m+y;

}

int bfs(int x,int y)

{

flag[x][y]=true;

if (!head && !tail) q[++head]=get(x,y),++tail;

while (head<=tail)

{

int X=ceil(q[head]*1.0/m),Y=q[head]%m;

if (!Y) Y=m;

flag[X][Y]=true;

if (s[X-1][Y]=='#' && !flag[X-1][Y]) q[++tail]=get(X-1,Y);

if (s[X+1][Y]=='#' && !flag[X+1][Y]) q[++tail]=get(X+1,Y);

if (s[X][Y-1]=='#' && !flag[X][Y-1]) q[++tail]=get(X,Y-1);

if (s[X][Y+1]=='#' && !flag[X][Y+1]) q[++tail]=get(X,Y+1);

++head;

}

return tail;

}

int main()

{

scanf("%d%d",&n,&m);

for (int i=1;i<=n;++i) scanf("%s",s[i]+1);

for (int i=1;i<=n;++i)

for (int j=1;j<=m;++j)

if (s[i][j]=='#' && !flag[i][j])

{

memset(q,0,sizeof(q)),head=tail=0;

int t=bfs(i,j);

if (t==1 || t==2) ++ans;

}

return printf("%d",ans),0;

}

3421：螺旋加密

题目大意：给出一行只包含大写字母和空格的字符串，每个字符和数字一一对应，空格对应0，A对应1，B对应2，依此类推，再将每个字符对应的数转换为5位二进制数，拼接形成新字符串，将新字符串按照螺旋矩阵的填充方式填充进n行m列的矩阵中

其实应该算是1A，数据范围写的是最大20行20列，但是测试数据有大于20的，把数组大小改为30秒过，基本上按照题意模拟，因为字符串保证在矩阵范围内，所以无须担心二进制数会超出矩阵填充范围，按照右下左上的顺序进行填充即可

#include<cstdio>
#include<string>
#include<iostream>
using namespace std;
int r,c,ans[31][31];
string s,t="",dir="right";

void get_binary(int x)
{
	int num[6]={0},tot=0;
	while (x) num[++tot]=x%2,x/=2;
	for (int i=5;i;--i) t+=num[i]+'0';
}

int main()
{
	int posx=1,posy=1;
	scanf("%d%d",&r,&c),getchar(),getline(cin,s);
	for (int i=1;i<=r;++i)
	  for (int j=1;j<=c;++j) ans[i][j]=-1;
	for (int i=0;i<s.length();++i)
	  if (s[i]==' ') get_binary(0);
	  else get_binary(s[i]-'A'+1);
	for (int i=0;i<t.length();++i)
	  {
	  	ans[posx][posy]=t[i]-'0';
	  	if (dir=="right") 
	  	  if (posy<c && ans[posx][posy+1]==-1) ++posy;
	  	  else dir="down",++posx;
	  	else if (dir=="down")
	  	  if (posx<r && ans[posx+1][posy]==-1) ++posx;
	  	  else dir="left",--posy;
	  	else if (dir=="left")
	  	  if (posy>0 && ans[posx][posy-1]==-1) --posy;
	  	  else dir="up",--posx;
	  	else if (dir=="up")
	  	  if (posx>0 && ans[posx-1][posy]==-1) --posx;
	  	  else dir="right",++posy;
	  }
	for (int i=1;i<=r;++i)
	  for (int j=1;j<=c;++j) printf("%d",ans[i][j]!=-1?ans[i][j]:0);
	return 0;
}

#include<cstdio>

#include<string>

#include<iostream>

using namespace std;

int r,c,ans[31][31];

string s,t="",dir="right";

void get_binary(int x)

{

int num[6]={0},tot=0;

while (x) num[++tot]=x%2,x/=2;

for (int i=5;i;--i) t+=num[i]+'0';

}

int main()

{

int posx=1,posy=1;

scanf("%d%d",&r,&c),getchar(),getline(cin,s);

for (int i=1;i<=r;++i)

for (int j=1;j<=c;++j) ans[i][j]=-1;

for (int i=0;i<s.length();++i)

if (s[i]==' ') get_binary(0);

else get_binary(s[i]-'A'+1);

for (int i=0;i<t.length();++i)

{

ans[posx][posy]=t[i]-'0';

if (dir=="right")

if (posy<c && ans[posx][posy+1]==-1) ++posy;

else dir="down",++posx;

else if (dir=="down")

if (posx<r && ans[posx+1][posy]==-1) ++posx;

else dir="left",--posy;

else if (dir=="left")

if (posy>0 && ans[posx][posy-1]==-1) --posy;

else dir="up",--posx;

else if (dir=="up")

if (posx>0 && ans[posx-1][posy]==-1) --posx;

else dir="right",++posy;

}

for (int i=1;i<=r;++i)

for (int j=1;j<=c;++j) printf("%d",ans[i][j]!=-1?ans[i][j]:0);

return 0;

}

2021.2.3

3427：B

题目大意：给出5种操作，新建序列，添加序列元素，合并两个序列，输出排序后序列元素和对序列去重

一开始用的vector，但是MLE了，后来发现可以用list，然后用list过了

#include<cstdio>
#include<list>
#include<algorithm>
using namespace std;
#define N 10010
int n;
list<int>a[N];
list<int>::iterator new_end;
int main()
{
	char s[10];
	int x,y;
	scanf("%d",&n);
	while (n--)
	  {
	  	scanf("%s%d",s,&x);
	  	if (s[0]=='n') continue;
	  	if (s[0]=='a') scanf("%d",&y),a[x].push_back(y);
	  	if (s[0]=='m') scanf("%d",&y),a[x].sort(),a[y].sort(),a[x].merge(a[y]);
		if (s[0]=='u') a[x].sort(),a[x].unique();
		if (s[0]=='o') 
		  {
		  	a[x].sort();
		  	for (list<int>::iterator i=a[x].begin();i!=a[x].end();++i) printf("%d ",*i);
		  	printf("\n");
		  }
	  }
	return 0;
}

#include<cstdio>

#include<list>

#include<algorithm>

using namespace std;

#define N 10010

int n;

list<int>a[N];

list<int>::iterator new_end;

int main()

{

char s[10];

int x,y;

scanf("%d",&n);

while (n--)

{

scanf("%s%d",s,&x);

if (s[0]=='n') continue;

if (s[0]=='a') scanf("%d",&y),a[x].push_back(y);

if (s[0]=='m') scanf("%d",&y),a[x].sort(),a[y].sort(),a[x].merge(a[y]);

if (s[0]=='u') a[x].sort(),a[x].unique();

if (s[0]=='o')

{

a[x].sort();

for (list<int>::iterator i=a[x].begin();i!=a[x].end();++i) printf("%d ",*i);

printf("\n");

}

return 0;

}

总结：①vector采用的连续存储空间，可以用[]获取元素，插入和删除代价大，需要复制内存空间中的元素，导致占用内存过大，但随机访问快，时间复杂度 $O(1)$ ②list实现采用的是双向链表，随机访问慢，但是插入和删除较快，无需复制内存中元素，所以可以用list过

2021.2.6

4018：子串

题目大意：给出两个字符串S和T，问在T中删除任意字符能不能得到S

普通的贪心做法，尽可能地找靠前的能和S匹配上的字符，交了一发WA了之后调了一下错，不知道为什么出了一组zero ozreozre把我的程序hack掉了，然后改过来过了

#include<cstdio>
#include<cstring>
using namespace std;
char s[510],t[510];
int main()
{
	while (~scanf("%s%s",s+1,t+1))
	  {
	  	int n=strlen(s+1),m=strlen(t+1),head1=1,head2=1;
	  	while (1)
	  	  {
	  	  	if (t[head2]==s[head1]) ++head1,++head2;
	  	  	if (t[head2]!=s[head1]) ++head2; 
	  	  	if (head1>n || head2>m) break;
		  }
		if (head1>n) printf("Yes\n");
		else printf("No\n");
	  }
	return 0;
}

#include<cstdio>

#include<cstring>

using namespace std;

char s[510],t[510];

int main()

{

while (~scanf("%s%s",s+1,t+1))

{

int n=strlen(s+1),m=strlen(t+1),head1=1,head2=1;

while (1)

{

if (t[head2]==s[head1]) ++head1,++head2;

if (t[head2]!=s[head1]) ++head2;

if (head1>n || head2>m) break;

}

if (head1>n) printf("Yes\n");

else printf("No\n");

}

return 0;

}

4021：最大乘积

题目大意：从整数序列中删除一个数使得整个序列乘积最大，如果有多种选择输出输入最靠前的那个

里面太多坑了，考虑多个0，一个0奇数个负数，一个0偶数个负数无正数，一个0偶数个负数有正数等等，自己查出来一个错，看提示查出来两个，总之情况很多，分类讨论吧

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 110
typedef long long LL;
int T,n;
LL a[N];
int main()
{
	scanf("%d",&T);
	while (T--)
	  {
	  	int count0=0;
	  	scanf("%d",&n);
	  	for (int i=1;i<=n;++i) 
	  	  {
	  	  	cin>>a[i];
	  	  	if (!a[i]) ++count0;
		  }
		if (count0>1) 
		  {
		  	cout<<a[1]<<endl;
		  	continue;
		  }
		else if (count0==1) 
		  {
		  	LL sum=1LL;
		  	for (int i=1;i<=n;++i)
		  	  if (a[i]<0) sum*=-1;
		  	if (sum==1LL) 
			  {
			  	printf("0\n");
			  	continue;
			  }
			else
			  for (int i=1;i<=n;++i)
			    if (a[i]) 
			      {
			      	cout<<a[i]<<endl;
			      	break;
				  }
		  }
		else
		  {
		  	LL sum=1LL;
		  	int count_neg=0;
		  	for (int i=1;i<=n;++i)
		  	  if (a[i]<0) sum=-sum,++count_neg;
		  	if (sum==1LL)
		  	  if (count_neg==n)
		  	    {
		  	    	LL ans=1e7;
		  	    	for (int i=1;i<=n;++i) ans=min(ans,a[i]);
		  	    	cout<<ans<<endl;
				}
			  else
			    {
			    	LL ans=1e7;
			    	for (int i=1;i<=n;++i)
			    	  if (a[i]>0 && a[i]<ans) ans=a[i];
			    	cout<<ans<<endl;
				}
			else
			  {
			  	LL ans=-1e7;
			  	for (int i=1;i<=n;++i)
			  	  if (a[i]<0 && a[i]>ans) ans=a[i];
			  	cout<<ans<<endl;
			  }
		  }
	  }
	return 0;
}

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

#define N 110

typedef long long LL;

int T,n;

LL a[N];

int main()

{

scanf("%d",&T);

while (T--)

{

int count0=0;

scanf("%d",&n);

for (int i=1;i<=n;++i)

{

cin>>a[i];

if (!a[i]) ++count0;

}

if (count0>1)

{

cout<<a[1]<<endl;

continue;

}

else if (count0==1)

{

LL sum=1LL;

for (int i=1;i<=n;++i)

if (a[i]<0) sum*=-1;

if (sum==1LL)

{

printf("0\n");

continue;

}

else

for (int i=1;i<=n;++i)

if (a[i])

{

cout<<a[i]<<endl;

break;

}

else

{

LL sum=1LL;

int count_neg=0;

for (int i=1;i<=n;++i)

if (a[i]<0) sum=-sum,++count_neg;

if (sum==1LL)

if (count_neg==n)

{

LL ans=1e7;

for (int i=1;i<=n;++i) ans=min(ans,a[i]);

cout<<ans<<endl;

}

else

{

LL ans=1e7;

for (int i=1;i<=n;++i)

if (a[i]>0 && a[i]<ans) ans=a[i];

cout<<ans<<endl;

}

else

{

LL ans=-1e7;

for (int i=1;i<=n;++i)

if (a[i]<0 && a[i]>ans) ans=a[i];

cout<<ans<<endl;

}

return 0;

}

2021.2.7

2776：统计字符

题目大意：给出一段C++程序，用来统计数字字符串中0出现的次数以及最大出现次数的数是什么

不解释了

#include<iostream>
using namespace std;
int main()
{
    cout<<"m%10"<<endl<<"t"<<endl;
    return 0;
}

#include<iostream>

using namespace std;

int main()

{

cout<<"m%10"<<endl<<"t"<<endl;

return 0;

}

4033：铺地毯

题目大意：给出二维坐标系下的地毯坐标，问某个坐标最上面的地毯是第几个地毯

循环遍历地毯是否覆盖该点即可，由于没有数据范围，一开始T了，后来开到1w过了

#include<cstdio>
using namespace std;
#define N 10010
int n,ans=-1;
struct data
{
	int a,b,g,k;
}s[N];
int main()
{
	int x,y;
	scanf("%d",&n);
	for (int i=1;i<=n;++i) scanf("%d%d%d%d",&s[i].a,&s[i].b,&s[i].g,&s[i].k);
	scanf("%d%d",&x,&y);
	for (int i=1;i<=n;++i)
	  if (x>=s[i].a && x<=s[i].a+s[i].g && y>=s[i].b && y<=s[i].b+s[i].k) ans=i;
	return printf("%d",ans),0;
}

#include<cstdio>

using namespace std;

#define N 10010

int n,ans=-1;

struct data

{

int a,b,g,k;

}s[N];

int main()

{

int x,y;

scanf("%d",&n);

for (int i=1;i<=n;++i) scanf("%d%d%d%d",&s[i].a,&s[i].b,&s[i].g,&s[i].k);

scanf("%d%d",&x,&y);

for (int i=1;i<=n;++i)

if (x>=s[i].a && x<=s[i].a+s[i].g && y>=s[i].b && y<=s[i].b+s[i].k) ans=i;

return printf("%d",ans),0;

}

4072：判断多个点是否在同一直线

题目大意：如题

我的思路是直接统计每个点与第一个点的直线斜率，如果一样则在，否则不在，由初中数学知识可知tan90°不存在，所以设置int的最大值作为直线斜率不存在，所以该程序理论上是可以被hack掉的，前提是看过代码才能hack掉，避免hack的做法就是加一个标记变量来标记一下，但是懒得加了...

#include<cstdio>
#include<cmath>
using namespace std;
#define eps 1e-6
#define N 110
#define inf 0x7fffffff
int T,n;
double k;
struct data
{
	int X,Y;
}a[N];

double get(data x,data y)
{
	return x.X==y.X?inf:(y.Y-x.Y)*1.0/(y.X-x.X);
}

int main()
{
	scanf("%d",&T);
	while (T--)
	  {
	  	scanf("%d",&n);
	  	for (int i=1;i<=n;++i) scanf("%d%d",&a[i].X,&a[i].Y);
	  	k=get(a[1],a[2]);
	  	if (n==1 || n==2) 
	  	  {
	  	  	printf("True\n");
	  	  	continue;
		  }
		bool flag=false;
	  	for (int i=3;i<=n;++i) 
	  	  if (fabs(k-get(a[i],a[1]))<eps) continue;
	  	  else 
	  	    {
	  	    	flag=true;
	  	    	break;
			}
		printf(flag?"False\n":"True\n");
	  }
	return 0;
}

#include<cstdio>

#include<cmath>

using namespace std;

#define eps 1e-6

#define N 110

#define inf 0x7fffffff

int T,n;

double k;

struct data

{

int X,Y;

}a[N];

double get(data x,data y)

{

return x.X==y.X?inf:(y.Y-x.Y)*1.0/(y.X-x.X);

}

int main()

{

scanf("%d",&T);

while (T--)

{

scanf("%d",&n);

for (int i=1;i<=n;++i) scanf("%d%d",&a[i].X,&a[i].Y);

k=get(a[1],a[2]);

if (n==1 || n==2)

{

printf("True\n");

continue;

}

bool flag=false;

for (int i=3;i<=n;++i)

if (fabs(k-get(a[i],a[1]))<eps) continue;

else

{

flag=true;

break;

}

printf(flag?"False\n":"True\n");

}

return 0;

}

2021.2.8

4008：糖果

题目大意：给出一个序列表示糖果数，求能取到的恰好为K的整数倍的最大糖果数，取糖果每次只能全部取

我果然是卡内存和时间的一把好手，一道背包DP硬是用记忆化搜索+各种剪枝交了8发卡过了，从K的最大整数倍往小dfs，状态为剩余糖果数和当前处于第几包糖果，然后按照暴搜的思路，一开始MLE是因为开了两个map，而且下标是pair的那种，直接超64M内存，后来一想判断是否处理过的map并不需要，删掉卡进内存限制，有人要问为什么不用数组？~~（dfs状态最大数到1e8啊喂）~~，用了map肯定会慢一些，所以每次查询map的时间复杂度为 $O(logn)$ ，用数组则是 $O(1)$ ，因为是记(shi)忆(ji)化(shi)搜(bao)索(sou)，所以出现过的状态直接用map的值返回，但是还是无奈TLE了，于是开始各种剪枝，如果不算记忆化搜索的状态，时间复杂度应为状态树的所有结点数之和，设序列总和为 $sum$ ，时间复杂度为 $O(\frac{sum}{k}*2^n)$ ，但是很容易想到两个剪枝条件，一个是当前x为负数时，不管选不选剩下的糖果都不可能为0了，直接返回-1，另一个是当前x比后面糖果数加起来都要多，即使全选也不可能为0，直接返回-1，当然因为数据弱就暴搜A了

正解：dp[i][j]表示前i个数能产生的和对k取模等于j的最大值，状态转移方程 $dp[i][j]=max(dp[i-1][(j+value[i])%k]+value[i],dp[i-1][j])$ ， $dp[0][0]=0$ .

#include<cstdio>
#include<map>
using namespace std;
#define N 110
int n,k,a[N],sum,s[N];
map<pair<int,int>,int>G;

int dfs(int x,int now)
{
	if (x>sum-s[now]) return G[make_pair(x,now)]=-1;
	else if (x==sum-s[now]) return G[make_pair(x,now)]=1;
	if (x<0) return G[make_pair(x,now)]=-1;
	if (G[make_pair(x,now)]) return G[make_pair(x,now)];
	if (!x) return G[make_pair(x,now)]=1;
	if (x && now==n) return G[make_pair(x,n)]=-1;
	int f1=dfs(x-a[now+1],now+1),f2=dfs(x,now+1);
	if (f1==1 || f2==1) G[make_pair(x,now)]=1;
	else G[make_pair(x,now)]=-1;
	return G[make_pair(x,now)];
}

int main()
{
	bool flag=false;
	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;++i) scanf("%d",&a[i]),sum+=a[i],s[i]=sum;
	for (int i=sum/k*k;i>=k;i-=k)
	  if (dfs(i,0)==1) 
	    {
	    	flag=true,printf("%d",i);
	    	break;
		}
	if (!flag) printf("0");
	return 0;	  
}

#include<cstdio>

#include<map>

using namespace std;

#define N 110

int n,k,a[N],sum,s[N];

map<pair<int,int>,int>G;

int dfs(int x,int now)

{

if (x>sum-s[now]) return G[make_pair(x,now)]=-1;

else if (x==sum-s[now]) return G[make_pair(x,now)]=1;

if (x<0) return G[make_pair(x,now)]=-1;

if (G[make_pair(x,now)]) return G[make_pair(x,now)];

if (!x) return G[make_pair(x,now)]=1;

if (x && now==n) return G[make_pair(x,n)]=-1;

int f1=dfs(x-a[now+1],now+1),f2=dfs(x,now+1);

if (f1==1 || f2==1) G[make_pair(x,now)]=1;

else G[make_pair(x,now)]=-1;

return G[make_pair(x,now)];

}

int main()

{

bool flag=false;

scanf("%d%d",&n,&k);

for (int i=1;i<=n;++i) scanf("%d",&a[i]),sum+=a[i],s[i]=sum;

for (int i=sum/k*k;i>=k;i-=k)

if (dfs(i,0)==1)

{

flag=true,printf("%d",i);

break;

}

if (!flag) printf("0");

return 0;

}

总结：①暴搜过后一定要考虑剪枝，说不定就能过

发个提交截图开心一下

2021.2.9

4010：2011

题目大意：给出不超过200位的整数n，求 $2011^n$ 的最后四位，去除前导零

很明显快速幂，但是这里我们的指数太大了无法用long long表示，不能直接用快速幂，由费马小定理得，当 $p$ 为质数且 $(a,p)=1$ 时， $a^n\equiv 1\pmod{p}$ 成立的最小正整数解 $n=p-1$ ，此时这个正整数解称为 $a$ 模 $p$ 的阶，记为 $ord_pa=n$ ，实际上我们取最后四位需要对最终结果%1w，但是1w并不是质数，由欧拉定理得， $ord_pa=n$ ，则 $a^n\equiv 1\pmod{p}$ 当且仅当 $p|n$ ，这个定理说明了一个问题，当我们每次对 $a$ 乘“阶”方的时候，在模 $p$ 意义下 $a^n$ 的值完成了一次循环，而欧拉定理告诉我们，这个阶是 $p$ 的因数，所以我们只需要关心对指数%p之后的数的乘积情况，实际上要求这个阶需要用BSGS算法，到这里就可以完美地使用快速幂了，虽然程序很简单，但是背后的数学理论非常深厚

#include<cstdio>
#include<iostream>
#include<string>
using namespace std;
typedef long long LL;
#define mod 10000LL
int T;
string n;

LL qpow(LL x,LL y)
{
	if (!y) return 1LL;
	if (y==1) return x%mod;
	LL t=qpow(x,y/2);
	if (y&1) return t*t%mod*x%mod;
	else return t*t%mod;
}

int main()
{
	int t;
	scanf("%d",&T);
	while (T--) 
	  {
	  	cin>>n;
		if (n.length()>4) t=atoi(n.substr(n.length()-4,4).c_str());
		else t=atoi(n.c_str());
		cout<<qpow(2011LL,(LL)t)<<endl;
	  }
	return 0;
}

#include<cstdio>

#include<iostream>

#include<string>

using namespace std;

typedef long long LL;

#define mod 10000LL

int T;

string n;

LL qpow(LL x,LL y)

{

if (!y) return 1LL;

if (y==1) return x%mod;

LL t=qpow(x,y/2);

if (y&1) return t*t%mod*x%mod;

else return t*t%mod;

}

int main()

{

int t;

scanf("%d",&T);

while (T--)

{

cin>>n;

if (n.length()>4) t=atoi(n.substr(n.length()-4,4).c_str());

else t=atoi(n.c_str());

cout<<qpow(2011LL,(LL)t)<<endl;

}

return 0;

}

总结：①终于用费马小定理和欧拉定理完美解释了为什么要对指数也取模来完成快速幂√

4041：矩阵运算

题目大意：给出俩矩阵求矩乘和矩置

日常摸鱼

#include<cstdio>
#include<iostream>
#include<iomanip>
using namespace std;
#define N 110
int x1,y1,x2,y2,a[N][N],b[N][N],c[N][N];

void getc()
{
	for (int i=1;i<=x1;++i)
	  for (int j=1;j<=y2;++j)
	    for (int k=1;k<=y1;++k) c[i][j]+=a[i][k]*b[k][j];
}

int main()
{
	scanf("%d%d",&x1,&y1);
	for (int i=1;i<=x1;++i)
	  for (int j=1;j<=y1;++j) scanf("%d",&a[i][j]);
	scanf("%d%d",&x2,&y2);
	for (int i=1;i<=x2;++i)
	  for (int j=1;j<=y2;++j) scanf("%d",&b[i][j]);
	if (y1==x2)
	  {
	  	getc();
	  	for (int i=1;i<=y2;++i)
	  	  {
	  	  	for (int j=1;j<=x1;++j) cout<<setw(5)<<c[j][i];
	  	  	cout<<endl;
		  }
	  }
	else
	  for (int i=1;i<=y1;++i)
	    {
	    	for (int j=1;j<=x1;++j) cout<<setw(5)<<a[j][i];
	    	cout<<endl;
		}
	return 0;
}

#include<cstdio>

#include<iostream>

#include<iomanip>

using namespace std;

#define N 110

int x1,y1,x2,y2,a[N][N],b[N][N],c[N][N];

void getc()

{

for (int i=1;i<=x1;++i)

for (int j=1;j<=y2;++j)

for (int k=1;k<=y1;++k) c[i][j]+=a[i][k]*b[k][j];

}

int main()

{

scanf("%d%d",&x1,&y1);

for (int i=1;i<=x1;++i)

for (int j=1;j<=y1;++j) scanf("%d",&a[i][j]);

scanf("%d%d",&x2,&y2);

for (int i=1;i<=x2;++i)

for (int j=1;j<=y2;++j) scanf("%d",&b[i][j]);

if (y1==x2)

{

getc();

for (int i=1;i<=y2;++i)

{

for (int j=1;j<=x1;++j) cout<<setw(5)<<c[j][i];

cout<<endl;

}

else

for (int i=1;i<=y1;++i)

{

for (int j=1;j<=x1;++j) cout<<setw(5)<<a[j][i];

cout<<endl;

}

return 0;

}

2021.2.13

1003：Hangover

题目大意：翻译过来就是 $\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}$ ，给出一个浮点数Q，求比Q大的第一个n是多少

日常划水

#include<cstdio>
using namespace std;
double a[310],n;
int main()
{
	for (int i=1;i<=300;++i) a[i]=a[i-1]+1.0/(i+1);
	while (~scanf("%lf",&n)) 
	  {
	  	if (!(n>0)) break;
	  	int l=1,r=300;
	  	while (l<=r)
	  	  {
	  	  	int mid=(l+r)>>1;
	  	  	if (a[mid]>=n) r=mid-1;
	  	  	else l=mid+1;
		  }
		printf("%d card(s)\n",r+1);
	  }
	return 0;
}

#include<cstdio>

using namespace std;

double a[310],n;

int main()

{

for (int i=1;i<=300;++i) a[i]=a[i-1]+1.0/(i+1);

while (~scanf("%lf",&n))

{

if (!(n>0)) break;

int l=1,r=300;

while (l<=r)

{

int mid=(l+r)>>1;

if (a[mid]>=n) r=mid-1;

else l=mid+1;

}

printf("%d card(s)\n",r+1);

}

return 0;

}

1019：Number Sequence

题目大意：一个长度为n的数字串由S1S2...Sk的数字组组成，每个数字组Si由1~i的所有数拼接而成，给出n，求数字串第n位的数字是什么

数字串的长度可以简单地递推出来，确定在第几个数字组之后，可以直接暴力查是第几个数，由于数据范围为int最大值，预处理需要 $\sqrt {inf}$ ，大约是5w个，最多10组数据，最坏时间复杂度 $O(T\sqrt {inf})$ ，最坏在 $10^6$ ，也能过的，然而交上去发现运行时间比其他人还要短

#include<cstdio>
using namespace std;
typedef long long LL;
int T,n;
LL a[50000],sum[50000];

LL get(LL x)
{
	LL count=0;
	if (!x) return 1LL;
	while (x) ++count,x/=10;
	return count;
}

int find(LL x)
{
	int l=1,r=49999;
	while (l<=r)
	  {
	  	int mid=(l+r)>>1;
	  	if (sum[mid]>=x) r=mid-1;
	  	else l=mid+1;
	  }
	return r+1;
}

int find_digit(int x,int pos)
{
	int num[11]={0},tot=0;
	if (!x) num[++tot]=0;
	while (x) num[++tot]=x%10,x/=10;
	return num[tot-pos+1];
}

int main()
{
	scanf("%d",&T),a[1]=1LL;
	for (int i=2;i<50000;++i) a[i]=a[i-1]+get(i);
	for (int i=1;i<50000;++i) sum[i]=sum[i-1]+a[i];
	while (T--)
	  {
	  	scanf("%d",&n);
	  	int x=find((LL)n),y=(int)((LL)n-sum[x-1]);
	  	for (int i=1;y;++i)
	  	  if (y>get(i)) y-=get(i);
	  	  else 
	  	    {
	  	    	printf("%d\n",find_digit(i,y));
	  	    	break;
			}
	  }
	return 0;
}

#include<cstdio>

using namespace std;

typedef long long LL;

int T,n;

LL a[50000],sum[50000];

LL get(LL x)

{

LL count=0;

if (!x) return 1LL;

while (x) ++count,x/=10;

return count;

}

int find(LL x)

{

int l=1,r=49999;

while (l<=r)

{

int mid=(l+r)>>1;

if (sum[mid]>=x) r=mid-1;

else l=mid+1;

}

return r+1;

}

int find_digit(int x,int pos)

{

int num[11]={0},tot=0;

if (!x) num[++tot]=0;

while (x) num[++tot]=x%10,x/=10;

return num[tot-pos+1];

}

int main()

{

scanf("%d",&T),a[1]=1LL;

for (int i=2;i<50000;++i) a[i]=a[i-1]+get(i);

for (int i=1;i<50000;++i) sum[i]=sum[i-1]+a[i];

while (T--)

{

scanf("%d",&n);

int x=find((LL)n),y=(int)((LL)n-sum[x-1]);

for (int i=1;y;++i)

if (y>get(i)) y-=get(i);

else

{

printf("%d\n",find_digit(i,y));

break;

}

return 0;

}

2021.2.28

1005：I Think I Need a Houseboat

题目大意：给出一个坐标，有一个以原点为圆心，半径每年逐步扩张的存在于第一二象限的半圆，求第几年半圆会将该坐标包含，半圆每年扩张50平方英里

题意叙述得不像人话，凑合着看吧，计算出坐标所需的半圆半径，然后看有多少个50的倍数就是用几年

#include<cstdio>
#include<cmath>
using namespace std;
int T;
double X,Y;
int main()
{
	scanf("%d",&T);
	for (int i=1;i<=T;++i)
	  {
	  	scanf("%lf%lf",&X,&Y);
	  	double R=sqrt(X*X+Y*Y);
	  	printf("Property %d: This property will begin eroding in year %d. \n",i,(int)ceil(3.1415926*R*R/50.0/2));
	  }
	return printf("END OF OUTPUT."),0;
}

#include<cstdio>

#include<cmath>

using namespace std;

int T;

double X,Y;

int main()

{

scanf("%d",&T);

for (int i=1;i<=T;++i)

{

scanf("%lf%lf",&X,&Y);

double R=sqrt(X*X+Y*Y);

printf("Property %d: This property will begin eroding in year %d. \n",i,(int)ceil(3.1415926*R*R/50.0/2));

}

return printf("END OF OUTPUT."),0;

}

总结：①C++用ceil函数输出%d输出需要强制类型转换

1089：Intervals

题目大意：区间合并

排序，记录左右端点，遍历

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
#define N 50010
int n;
struct data
{
	int X,Y;
}a[N];
vector<data>ans;

bool cmp(data x,data y)
{
	return x.X==y.X?x.Y<y.Y:x.X<y.X;
}

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;++i) scanf("%d%d",&a[i].X,&a[i].Y);
	sort(a+1,a+n+1,cmp);
	int l=a[1].X,r=a[1].Y;
	for (int i=2;i<=n;++i)
	  if (a[i].X<=r) r=max(r,a[i].Y);
	  else ans.push_back((data){l,r}),l=a[i].X,r=a[i].Y;
	if (l && r) ans.push_back((data){l,r});
	sort(ans.begin(),ans.end(),cmp);
	for (int i=0;i<ans.size()-1;++i) printf("%d %d\n",ans[i].X,ans[i].Y);
	return printf("%d %d",ans[ans.size()-1].X,ans[ans.size()-1].Y),0;
}

#include<cstdio>

#include<algorithm>

#include<vector>

using namespace std;

#define N 50010

int n;

struct data

{

int X,Y;

}a[N];

vector<data>ans;

bool cmp(data x,data y)

{

return x.X==y.X?x.Y<y.Y:x.X<y.X;

}

int main()

{

scanf("%d",&n);

for (int i=1;i<=n;++i) scanf("%d%d",&a[i].X,&a[i].Y);

sort(a+1,a+n+1,cmp);

int l=a[1].X,r=a[1].Y;

for (int i=2;i<=n;++i)

if (a[i].X<=r) r=max(r,a[i].Y);

else ans.push_back((data){l,r}),l=a[i].X,r=a[i].Y;

if (l && r) ans.push_back((data){l,r});

sort(ans.begin(),ans.end(),cmp);

for (int i=0;i<ans.size()-1;++i) printf("%d %d\n",ans[i].X,ans[i].Y);

return printf("%d %d",ans[ans.size()-1].X,ans[ans.size()-1].Y),0;

}

总结：①排序时可能左端点靠后的区间的右端点比前面区间的右端点靠前，这时要取max

2021.3.12

2994：拼装模型

题目大意：合并果子

#include<cstdio>
#include<queue>
using namespace std;
priority_queue<int,vector<int>,greater<int> >q;
int n,ans;
int main()
{
	int x,y;
	scanf("%d",&n);
	for (int i=1;i<=n;++i) scanf("%d",&x),q.push(x);
	while (q.size()!=1)
	  {
	  	int x=q.top();
	  	q.pop();
	  	int y=q.top();
	  	q.pop(),ans+=x+y,q.push(x+y);
	  }
	return printf("%d",ans),0;
}

#include<cstdio>

#include<queue>

using namespace std;

priority_queue<int,vector<int>,greater<int> >q;

int n,ans;

int main()

{

int x,y;

scanf("%d",&n);

for (int i=1;i<=n;++i) scanf("%d",&x),q.push(x);

while (q.size()!=1)

{

int x=q.top();

q.pop();

int y=q.top();

q.pop(),ans+=x+y,q.push(x+y);

}

return printf("%d",ans),0;

}

2987：二项式系数

题目大意：求组合数的奇偶性

裸Lucas定理

#include<cstdio>
using namespace std;
int n,k,C[3][3];

int calc(int x,int y)
{
	if (x<3 && y<3) return C[x][y]%2;
	int t=calc(x/2,y/2);
	return t%2*calc(x%2,y%2)%2;
}

int main()
{
	C[1][0]=C[1][1]=C[2][0]=C[2][2]=1,C[2][1]=2;
	while (~scanf("%d%d",&n,&k)) printf("%d\n",calc(n,k));
	return 0;
}

#include<cstdio>

using namespace std;

int n,k,C[3][3];

int calc(int x,int y)

{

if (x<3 && y<3) return C[x][y]%2;

int t=calc(x/2,y/2);

return t%2*calc(x%2,y%2)%2;

}

int main()

{

C[1][0]=C[1][1]=C[2][0]=C[2][2]=1,C[2][1]=2;

while (~scanf("%d%d",&n,&k)) printf("%d\n",calc(n,k));

return 0;

}

2021.5.12

4100：进程检测

题目大意：给出n个进程的开始时间和结束时间，每个进程都需要在运行过程中进行测试，求最少经过多少次测试能把所有进程测试完

贪心，按照进程的开始时间进行排序，考虑一次测试最多能包括哪些进程，可以发现如果一次测试能把下一个进程包含，那么满足该进程的开始时间都小于等于前面所有进程的结束时间，如果不满足则该次测试不能包含该进程

#include<cstdio>
#include<algorithm>
using namespace std;
#define N 51
int T,n,ans;
struct data
{
	int st,ed;
}a[N];

bool cmp(data x,data y)
{
	return x.st<y.st;
}

int main()
{
	scanf("%d",&T);
	while (T--)
	  {
	  	scanf("%d",&n),ans=0;
	  	for (int i=1;i<=n;++i) scanf("%d%d",&a[i].st,&a[i].ed);
 	  	sort(a+1,a+n+1,cmp);
 	  	int last=1;
	  	++ans;
	  	for (int i=2;i<=n;++i)
	  	  for (int j=last;j<i;++j) 
	  	  	if (a[j].ed<a[i].st) 
			  {
				++ans,last=i;
				break; 	
			  } 
		printf("%d\n",ans);
	  }
	return 0;
}

#include<cstdio>

#include<algorithm>

using namespace std;

#define N 51

int T,n,ans;

struct data

{

int st,ed;

}a[N];

bool cmp(data x,data y)

{

return x.st<y.st;

}

int main()

{

scanf("%d",&T);

while (T--)

{

scanf("%d",&n),ans=0;

for (int i=1;i<=n;++i) scanf("%d%d",&a[i].st,&a[i].ed);

sort(a+1,a+n+1,cmp);

int last=1;

++ans;

for (int i=2;i<=n;++i)

for (int j=last;j<i;++j)

if (a[j].ed<a[i].st)

{

++ans,last=i;

break;

}

printf("%d\n",ans);

}

return 0;

}

DCrusher

Openjudge百练机试练习

2021.1.16

2021.1.17

2021.1.18

2021.1.19

2021.1.23

2021.1.25

2021.1.26

2021.1.27

2021.1.28

2021.1.29

2021.1.30

2021.1.31

2021.2.1

2021.2.2

2021.2.3

2021.2.6

2021.2.7

2021.2.8

2021.2.9

2021.2.13

2021.2.28

2021.3.12

2021.5.12

发表评论取消回复

2021.1.16

2021.1.17

2021.1.18

2021.1.19

2021.1.23

2021.1.25

2021.1.26

2021.1.27

2021.1.28

2021.1.29

2021.1.30

2021.1.31

2021.2.1

2021.2.2

2021.2.3

2021.2.6

2021.2.7

2021.2.8

2021.2.9

2021.2.13

2021.2.28

2021.3.12

2021.5.12

发表评论 取消回复

发表评论取消回复