A 恭喜小梁成为了宝可梦训练家~
题解：数据极小，sort即可
/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
const int maxn = 3100;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1000007;
using namespace std;
int a[maxn];
int main()
{
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int sum=0;
for(int i=0;i<n;i++) cin>>a[i],sum+=a[i];
sort(a,a+n);
printf("MAX:%d\n",a[n-1]);
printf("MIN:%d\n",a[0]);
printf("AVG:%.2f\n",(double)sum/(double)(n));
}
return 0;
}
B 皮(A)卡(C)皮(M)~
题解：用三个变量进行标记即可
/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
const int maxn = 3100;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1000007;
using namespace std;
string s;
int main()
{
int t;
cin>>t;
while(t--){
cin>>s;
bool a=false,m=false,c=false;
for(int i=0;i<s.size();i++){
if(s[i]=='A') a=true;
if(s[i]=='M') m=true;
if(s[i]=='C') c=true;
}
if(a&&m&&c) cout<<-1<<endl;
else if(!a) cout<<"A"<<endl;
else if(!m) cout<<"M"<<endl;
else if(!c) cout<<"C"<<endl;
}
return 0;
}
C 杰尼杰尼
题解：
注意这个题问的是交点个数，而不是多少条线段相交，
那么我们可以把求出来的交点储存在数组里，每次遍历看看这个点是不是已经计算过了，如果计算过了，直接跳过即可。
/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
const int maxn = 510;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 100000000;
using namespace std;
double a[maxn],b[maxn];
struct wazxy{
double x,y;
}rem[10010];
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i]>>b[i];
}
int ans=0,cnt=0;
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
if(a[i]!=a[j]){
double x=(b[j]-b[i])/(a[i]-a[j]);
double y=a[i]*((b[j]-b[i])/(a[i]-a[j]))+b[i];
bool flag=false;
for(int k=0;k<cnt;k++){
if(x==rem[k].x&&y==rem[k].y){
flag=true;
break;
}
}
if(!flag) ans++;
rem[cnt].x=x;
rem[cnt++].y=y;
}
}
}
if(ans==0) cout<<"No Fire Point."<<endl;
else cout<<ans<<endl;
return 0;
}
D 古代遗迹：字符王国
题解：双指针，因为t字符串顺序随意，所以我们统计t和s片段的字符数量有几个不同即可，每次检查片段对比一下他们序列不同的字符个数即可。
当整个片段往右移动的时候，减去最左边的字母，再加上右边的字母。
/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
const int maxn = 1e5+10;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 100000000;
using namespace std;
string s,k;
int cnt[500];
int num[500];
int main()
{
int t;
cin>>t;
while(t--){
cin>>s>>k;
memset(cnt,0,sizeof(cnt));
memset(num,0,sizeof(num));
for(int i=0;i<k.size();i++){
cnt[k[i]-'a']++;
}
int lens=s.size(),lenk=k.size();
int l=0,r=0;
int ans=0;
//for(int i=0;i<26;i++) cout<<cnt[i]<<" ";
num[s[0]-'a']++;
while(true){
if(r-l+1<lenk){
r++;
num[s[r]-'a']++;
}
else{
int cnt1=0;
for(int i=0;i<26;i++){
cnt1+=abs(cnt[i]-num[i]);
}
// for(int i=0;i<26;i++) cout<<num[i]<<" ";
// cout<<endl<<endl;;
// cout<<cnt1<<endl;
if(cnt1<=2) ans++;
l++,r++;
if(r==lens) break;
num[s[l-1]-'a']--;
num[s[r]-'a']++;
}
//cout<<l<<" "<<r<<endl;
}
cout<<ans<<endl;
}
return 0;
}
E 皮卡丘这么可爱，当然要.....
题解：这个题应该是一个多重背包+完全背包+01背包的结合体。
G 遗迹逃亡
这个题的话，问的是能否逃出，根路径长度无关，所以dfs可能会快一些。
dfs，bfs板子题。
/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
const int maxn = 510;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 100000000;
using namespace std;
char a[maxn][maxn];
bool visited[maxn][maxn];
bool flag=false;
int n,m;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
void dfs(int x,int y){
if(a[x][y]=='g'){
flag=true;
return ;
}
if(flag==true) return ;
for(int i=0;i<4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if((a[nx][ny]=='.'||a[nx][ny]=='g')&&!visited[nx][ny]){
visited[nx][ny]=true;
dfs(nx,ny);
}
}
}
int main()
{
cin>>n>>m;
memset(visited,false,sizeof(visited));
for(int i=1;i<=n;i++){
scanf("%s",a[i]+1);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]=='s'){
flag=false;
visited[i][j]=true;
dfs(i,j);
break;
}
}
}
if(flag) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return 0;
}
J 小梁的背包
题解：01背包问题，只需要开辟一个数组记录一下个数即可。
/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
const int maxn = 1e5+10;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 100000000;
using namespace std;
struct wazxy{
int w,v;
}a[maxn];
int dp[maxn],rem[maxn];
int main()
{
int t;
cin>>t;
while(t--){
int n,m;
cin>>n>>m;
for(int i=0;i<100000;i++){
dp[i]=0;
rem[i]=0;
}
for(int i=1;i<=n;i++) scanf("%d%d",&a[i].w,&a[i].v);
for(int i=1;i<=n;i++){
for(int j=m;j>=a[i].w;j--){
//dp[j]=max(dp[j],dp[j-a[i].w]+a[i].v);
if(dp[j]<dp[j-a[i].w]+a[i].v){
dp[j]=dp[j-a[i].w]+a[i].v;
rem[j]=rem[j-a[i].w]+1;
}
}
}
printf("%d %d\n",dp[m],rem[m]);
}
return 0;
}
L 小梁的道馆
题解：并查集模板题，建议使用路径压缩。
/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
const int maxn = 3100;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1000007;
using namespace std;
int f[maxn];
int ifind(int x){
if(x==f[x]) return x;
return f[x]=ifind(f[x]);
}
int main()
{
int n,m,k;
cin>>n>>m>>k;
for(int i=0;i<maxn-1;i++) f[i]=i;
for(int i=0;i<m;i++){
int x,y;
scanf("%d%d",&x,&y);
int dx=ifind(x);
int dy=ifind(y);
if(dx!=dy) f[dx]=dy;
}
for(int i=0;i<k;i++){
int x,y;
scanf("%d%d",&x,&y);
int dx=ifind(x);
int dy=ifind(y);
if(dx!=dy) printf("NO\n");
else printf("YES\n");
}
return 0;
}
京公网安备 11010502036488号