1 Ygg分苹果
#include <iostream>
using namespace std;
int main() {
int n;
cin>>n;
cout<<(1+n)*n/2;
}
2 最大公约数
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
int x,y,z;
cin>>x>>y>>z;
cout<<gcd(gcd(x,y),z)<<"\n";
}
3 软软的国旗
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n,m;
cin>>n>>m;
int flag=1;
int last=-1;
for(int i=1;i<=n;i++){
string s;
cin>>s;
s=" "+s;
int lflag=-1;
for(int j=1;j<=m;j++){
int tem=s[j]-'0';
if(lflag==-1){
lflag=tem;
}else if(lflag!=tem){
flag=0;
}
}
if(last!=-1&&last==lflag){
flag=0;
}
last=lflag;
}
if(flag){
cout<<"YES"<<"\n";
}else{
cout<<"NO"<<"\n";
}
}
4 79元能买什么
背包
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
int n;
cin>>n;
vector<int> dp(79+10);
for(int i=1;i<=n;i++){
int v,w;
cin>>v>>w;
for(int j=79;j>=v;j--){
dp[j]=max(dp[j-v]+w,dp[j]);
}
}
cout<<dp[79]<<"\n";
}
5 a+b?
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int a,b;
cin>>a>>b;
int maxx=0;
auto ex=[&](int x){
int res=0;
while(x){
res=max(res,x%10);
x/=10;
}
return res;
};
maxx=max(ex(a),ex(b))+1;
string ta=to_string(a),tb=to_string(b);
reverse(ta.begin(),ta.end());
reverse(tb.begin(),tb.end());
int y=0;
for(int i=0;i<max(ta.length(),tb.length());i++){
int na=((i>=ta.length())?0:(ta[i]-'0')),nb=((i>=tb.length())?0:(tb[i]-'0'));
int tem=y+na+nb;
y=tem/maxx;
}
int len=max(ta.length(),tb.length());
if(y){
len++;
}
cout<<len<<"\n";
}
6 卓卓子的特殊癖好
双指针
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n,m;
cin>>n>>m;
string s;
cin>>s;
s=" "+s;
int res=0;
int ans=0;
for(int l=1,r=0;l<=n;l++){
r=max(l-1,r);
while(res<m&&r<=n){
r++;
res+=(s[r]=='*');
}
if(r>n) {
break;
}
ans+=min(n-l+1,n-r+1);
if(r>=l){
res-=(s[l]=='*');
}
}
if(ans==0){
cout<<"This is really a regrettable thing."<<"\n";
}else{
cout<<ans<<"\n";
}
}
7 软院三大恶霸
bfs
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
map<vector<string>,int> k;
map<vector<string>,int> cnt;
vector<string> f(3);
for(int i=0;i<3;i++){
cin>>f[i];
}
k[f]=1;cnt[f]=0;
vector<string>ini(3);
ini[0]="lsh";
ini[1]="l*w";
ini[2]="qyq";
queue<vector<string>> q;
q.push(f);
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
int ans=0;
while(!q.empty()){
auto nw=q.front();
q.pop();
if(nw==ini){
ans=cnt[nw];
break;
}
int nx,ny;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
if(nw[i][j]=='*'){
nx=i,ny=j;
break;
}
}
}
for(int i=0;i<4;i++){
auto lx=nx+dx[i],ly=ny+dy[i];
auto lw=nw;
if(lx<0||lx>2||ly<0||ly>2){
continue;
}
swap(lw[nx][ny],lw[lx][ly]);
if(k[lw]){
continue;
}
k[lw]=1;
cnt[lw]=cnt[nw]+1;
q.push(lw);
}
}
cout<<ans<<"\n";
}
8 去漫展咯
前缀和
注意该题数据有点问题,实际上没有保证l和r小于n;
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n,m;
cin>>n>>m;
vector<int> f(n+1000000);
for(int i=1;i<=m;i++){
int l,r;
cin>>l>>r;
f[l]++,f[r+1]--;
}
int ans=0;
for(int i=1;i<=n;i++){
f[i]+=f[i-1];
ans=max(f[i],ans);
}
cout<<ans<<"\n";
}
9 分割数字
简单dp
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int n;
cin>>n;
string s;
cin>>s;
s=" "+s;
vector<vector<int>> f(n+10,vector<int>(n+10,-1));
f[0][0]=0;
for(int i=1;i<=n;i++){
int p=1;
int num=0;
for(int j=i-1;~j;j--){
num+=(s[(j+1)]-'0')*p;
p*=10;
for(int r=j;~r;r--){
if(r==0&&j!=0){
continue;
}
if((~f[j][r])&&f[j][r]<=num){
if(!(~f[i][r+1])){
f[i][r+1]=num;
}else{
f[i][r+1]=min(num,f[i][r+1]);
}
}
}
}
}
for(int i=n;i;i--){
if(~f[n][i]){
cout<<i<<"\n";
return 0;
}
}
}
}