@
目录题目链接
前言
本人菜鸡一个，写到一半吃饭去了(不吃饭后面的题也写不出来...),后续会补题
另附官方题解
A 智乃的Hello XXXX
题解
没啥说的直接输出
代码
print("hello ")
B 智乃买瓜
题解/思路
使用的算法：简单dp，类似于01背包（跟第一场的类似）。
定义状态：f(i,j)代表前i种瓜组成重量为j的方案数
状态转移方程
f(i,j)=f(i-1,j)+f(i-1,j-a[i]/2)+f(i,j-a[i])
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e3+10;
const int p=1e9+7;
int a[N],dp[N][N];
signed main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
dp[0][0]=1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
if(j>=a[i])
dp[i][j]=(dp[i-1][j-a[i]]+dp[i-1][j-a[i]/2]+dp[i-1][j])%p;
else if(j>=a[i]/2)
dp[i][j]=(dp[i-1][j-a[i]/2]+dp[i-1][j])%p;
else
dp[i][j]=dp[i-1][j];
}
}
for(int i=1;i<=m;i++)
cout<<dp[n][i]<<" ";
return 0;
}
（滚动数组优化）
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e3+10;
const int p=1e9+7;
int a[N],dp[N];
signed main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
dp[0]=1;
for(int i=1;i<=n;i++)
{
for(int j=m;j>=a[i]/2;j--)
{
//dp[j]=(dp[j-a[i]]+dp[j-a[i]/2]+dp[j])%p;
if(j>=a[i])
dp[j]=(dp[j-a[i]]+dp[j-a[i]/2]+dp[j])%p;
else if(j>=a[i]/2)
dp[j]=(dp[j-a[i]/2]+dp[j])%p;
}
}
for(int i=1;i<=m;i++)
cout<<dp[i]<<" ";
return 0;
}
D 智乃的01串打乱
题解/思路
直接找到第一个0和第一个1交换位置即可
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
int n;
string s;
cin>>n>>s;
int x,y;
for(int i=0;i<n;i++)
{
if(s[i]=='0'){x=i;break;}
}
for(int i=0;i<n;i++)
{
if(s[i]=='1'){y=i;break;}
}
swap(s[x],s[y]);
cout<<s<<endl;
return 0;
}
E智乃的数字积木(easy version)
题解/思路
简单题，直接分段排序，找到相同颜色的块然后排序
因为段与段之间不相交，则每次排序复杂度为O(nlog n)
还有一点就是大数取模的思路：
设x=abcd(分别是千，百，十，个位上的数)
x%p=a1000%p+b100%p+c10%p+d%p
=(((((a%p)10+b)%p10+c)%p*10)+d)%10
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
int col[N];
char s[N];
const int p=1e9+7;
int MOD(string str)
{
int len=str.length();
int s=0;
for(int i=0; i<len; i++)
{
s=s*10+str[i]-'0';
s=s%p;
}
return s;
}
bool cmp(char a,char b)
{
return a>b;
}
signed main()
{
int n,m,k;
cin>>n>>m>>k;
cin>>s;
for(int i=0;i<n;i++)
cin>>col[i];
for(int i=0;i<n;i++)
{
int j=i+1;
while(col[j]==col[i])
{
j++;
if(j==n){break;}
}
//cout<<i<<" "<<j<<endl;
sort(s+i,s+j,cmp);
i=j-1;
}
cout<<MOD(s)<<endl;
while(k--)
{
int p,q;
cin>>p>>q;
for(int i=0;i<n;i++)
if(col[i]==p)col[i]=q;
for(int i=0;i<n;i++)
{
int j=i+1;
while(col[j]==col[i])
{
j++;
if(j==n){break;}
}
sort(s+i,s+j,cmp);
i=j-1;
}
cout<<MOD(s)<<endl;
}
return 0;
}
G智乃的树旋转(easy version)
题解/思路
看题看题看题，题里有答案(看了n遍才明白的我是真的fw)
如果你看懂了的话你就会发现
当两棵树的两个节点互为父子关系的时候，输出父亲节点即可
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e3+10;
struct tree
{
int fa;
int l,r;
}t1[N],t2[N];
signed main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
int l,r;
cin>>l>>r;
t1[i].l=l;
t1[i],r=r;
t1[l].fa=i;
t1[r].fa=i;
}
for(int i=1;i<=n;i++)
{
int l,r;
cin>>l>>r;
t2[i].l=l;
t2[i],r=r;
t2[l].fa=i;
t2[r].fa=i;
}
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
{
if(t1[i].fa==j&&t2[j].fa==i)
{
cout<<"1"<<endl;
cout<<j<<endl;
return 0;
}
}
}
cout<<0<<endl;
return 0;
}
I 智乃的密码
题解/思路
题目要求我们找到包含三种类型的串，且长度∈[L,R]
设f(x)是每一个x位置上对应的f(x),区间[x,f(x)]满足题目要求，且区间[x,f(x)-1]不满足要求，(即每一个i对应的最小满足条件的j)
可以发现对于每一个j>i都有f(j)>=f(i)，具有单调性
这思路不就来了，二分分分~~~~
当然双指针(尺取)的方法更简单
但个人总想写二分(感觉更高端，bug更多....)
尺取和的思路都是找到每一个x位置对应的f(x)，然后算方案数
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
char s[N];
int a[N],b[N],c[N],d[N];
bool check(int l,int r)
{
int x=a[r]-a[l-1],y=b[r]-b[l-1],z=c[r]-c[l-1],p=d[r]-d[l-1];
if((x>=1&&y>=1&&z>=1)||(x>=1&&y>=1&&p>=1)||(y>=1&&z>=1&&p>=1)||(x>=1&&p>=1&&z>=1))
return 1;
return 0;
}
signed main()
{
int n,L,R;
cin>>n>>L>>R>>s+1;
for(int i=1;i<=n;i++)
{
a[i]=a[i-1];
b[i]=b[i-1];
c[i]=c[i-1];
d[i]=d[i-1];
if(s[i]>='A'&&s[i]<='Z')
a[i]++;
else if(s[i]>='a'&&s[i]<='z')
b[i]++;
else if(s[i]>='0'&&s[i]<='9')
c[i]++;
else
d[i]++;
//cout<<a[i]<<" "<<b[i]<<' '<<c[i]<<' '<<d[i]<<endl;
}
int ans=0;
for(int i=1;i<=n-L+1;i++)
{
int l=min(i+L-1,n),r=min(n,i+R-1);
int y=r;
while(l<r)
{
int mid=l+r>>1;
if(check(i,mid))
r=mid;
else
l=mid+1;
}
if(!check(i,l))continue;//没有满足题意的
ans+=y-l+1;
}
cout<<ans<<endl;
return 0;
}
L 智乃的数据库
题解/思路
因为题目的数据范围很小
所以我直接手写排序+去重(代码很丑，我自己都不想看，建议别看)
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
string s[1010];
int a[1010][1010];
char sql[50010],len;
map<string,int> q;
bool vis[1010];
struct xx
{
int a[1010],len;
}p[1010];
bool cmp(xx a,xx b)
{
for(int i=0;i<a.len;i++)
{
if(a.a[i]==b.a[i])continue;
return a.a[i]<b.a[i];
}
return 0;
}
bool xx(xx a,xx b)
{
for(int i=0;i<a.len;i++)
{
if(a.a[i]!=b.a[i])return 0;
}
return 1;
}
signed main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>s[i];
q[s[i]]=i;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
getchar();
scanf("SELECT COUNT(*) FROM Table GROUP BY ");
len=0;
int o=0;
while(cin>>sql[len])
{
if(sql[len]==',')
{
sql[len]='\0';
string ss=sql;
vis[q[ss]]=1;
len=0;
o++;
continue;
}
if(sql[len]==';')
{
sql[len]='\0';
string ss=sql;
vis[q[ss]]=1;
len=0;
o++;
break;
}
len++;
}
len=0;
for(int i=1;i<=n;i++)
{
int len=0;
for(int j=1;j<=m;j++)
{
if(vis[j])
{
p[i].a[len++]=a[i][j];
}
}
p[i].len=o;
}
sort(p+1,p+n+1,cmp);
int ans=1,x=1;
for(int i=2;i<=n;i++)
{
if(!xx(p[i],p[i-1]))
{
ans++;
}
}
cout<<ans<<endl;
for(int i=2;i<=n;i++)
{
if(xx(p[i],p[i-1]))//相等
{
x++;
}
else
{
cout<<x<<" ";
x=1;
}
}
cout<<x<<endl;
return 0;
}