程设代码纸质资料汇总

说明

明天考试，据说是有两个原题，我把代码自己重新敲了一遍（大部分），5个困难和模拟考试中等及以上没有重新敲一遍。

30题

总和分数

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int n;
	cin>>n;
	int sum=0;
	while(n--)
	{
		int a,b;
		cin>>a>>b;
		int res=(int)(1.0*a/b+0.5);
		sum+=res;
	}
	printf("2.0");
	return 0;
}

Petr读书

#include<bits/stdc++.h>

using namespace std;

int a[10];

int main()
{
	ios::sync_with_stdio(0);	cin.tie(0),cout.tie(0);
	
	int n;
	cin>>n;
	
	for(int i=1;i<=7;i++)	cin>>a[i];
	
	int sum=0,ans=0;
	while(sum<n)
	{
		for(int i=1;i<=n;i++)
		{
			sum+=a[i];
			if(sum>=n)
			{
				ans=i;
				break;
			}
		}
	}
	
	cout<<ans<<endl;
	
	return 0;
}

开心的金明

#include<bits/stdc++.h>

using namespace std;

const int N=150000+10;

int f[N];

int main()
{
	ios::sync_with_stdio(0);	cin.tie(0),cout.tie(0);
	
	int n,m;
	cin>>n>>m;
	
	for(int i=0;i<m;i++)
	{
		int v,w;
		cin>>v>>w;
		for(int j=n;j>=v;j--)
		{
			f[j]=max(f[j],f[j-v]+v*w);
		}
	}
	
	cout<<f[n]<<endl;
	
	return 0;
}

最小不重复值

#include<bits/stdc++.h>

using namespace std;

const int N=2e5+10;

int a[N],cnt[N],idx[N];

int main()
{
	ios::sync_with_stdio(0);	cin.tie(0),cout.tie(0);
	
	int n;
	cin>>n;
	
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		cnt[a[i]]++;
		idx[a[i]]=i;
	}
	
	int ans=-1;
	for(int i=1;i<=n;i++)
	{
		if(cnt[i]==1)
		{
			ans=idx[i];
			break;
		}
	}
	
	cout<<ans<<endl;
	
	return 0;
}

二维数组

#include<bits/stdc++.h>

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int x,y;
	scanf("%d,%d",&x,&y);
	int arr[x][y];
	
	for(int i=0;i<x;i++)
	{
		for(int j=0;j<y;j++)
		{
			arr[i][j]=i*j;
		}
	}
	
	cout<<"[";
	for(int i=0;i<x;i++)
	{
		cout<<"[";
		for(int j=0;j<y;j++)
		{
			cout<<arr[i][j];
			if(j!=y-1)	cout<<", ";
		}
		cout<<"]";
		if(i!=x-1)	cout<<", ";
	}
	cout<<"]";
	
	return 0;
}

产生每位数字相同的n位数

#include<bits/stdc++.h>

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	long long a,b;
	scanf("%lld,%lld",&a,&b);
	
	long long ans=0;
	for(int i=0;i<b;i++)
	{
		ans*=10;
		ans+=a;
	}
	
	cout<<ans<<endl;
	
	return 0;
}

海岸线的长度

#include<bits/stdc++.h>

using namespace std;

double distance(double x,double y,double a,double b)
{
	double ans=pow(x-a,2.0);
	double ans1=pow(y-b,2.0);
	double res=sqrt(ans+ans1);
	
	return res;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n;
	cin>>n;
	
	double x[10],y[10];
	for(int i=0;i<3;i++)
	{
		cin>>x[i]>>y[i];
	}
	double d1=distance(x[0],y[0],x[1],y[1]);
	double d2=distance(x[0],y[0],x[2],y[2]);
	double d3=distance(x[1],y[1],x[2],y[2]);
	
	double ans=d1+d2+d3;
	ans=(int)((ans+0.005)*100)/100.0;
	printf("%g\n",ans);
	
	return 0;
}

查找指定字符

#include<bits/stdc++.h>

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	char a[2],b[100];
	cin>>(a)>>(b);
	
	int q=-1,len=strlen(b);
	for(int i=0;i<len;i++)
	{
		if(a[0]==b[i])
		{
			q=i;
		}
	}
	
	if(q==-1)	cout<<"Not Found";
	else	cout<<"index = "<<q;
	
	return 0;
}

等价多米诺骨牌对的数量

#include<bits/stdc++.h>

using namespace std;

bool check(int a,int b)
{
	if(a==b||(a/10==b%10&&a%10==b/10))	return true;
	else	return false;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	string s;
	cin>>s;
	
	int len=s.size();
	vector<int> nums;
	for(int i=0;i<len;i++)
	{
		if(isdigit(s[i]))	//cout<<s[i];
			nums.push_back(s[i]-'0');
	}
	
	int len0=nums.size();
	//for(int i=0;i<len0;i++)	cout<<nums[i];
	
	vector<int> two;
	for(int i=0;i+1<len0;i+=2)
		two.push_back(nums[i]*10+nums[i+1]);
	
	//int len1=two.size();
	//for(int i=0;i<len1;i++)	cout<<two[i]<<endl;
	
	int len1=two.size();
	int cnt=0;
	for(int i=0;i<len1;i++)
	{
		for(int j=i+1;j<len1;j++)
		{
			if(check(two[i],two[j]))	cnt++;
		}
	}
	
	cout<<cnt<<endl;
	
	return 0;
}

找最小值

#include<bits/stdc++.h>

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n;
	cin>>n;
	int m=9999;
	for(int i=0;i<n;i++)
	{
		int x;
		cin>>x;
		if(x<m)
		{
			m=x;
		}
	}
	
	cout<<"min = "<<m;
	
	return 0;
}

神奇的方形补丁

#include<bits/stdc++.h>

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n;
	cin>>n;
	
	cout<<"[";
	for(int i=1;i<=n;i++)
	{
		cout<<"[";
		for(int j=1;j<=n;j++)
		{
			cout<<n;
			if(j!=n)	cout<<", ";
		}
		cout<<"]";
		if(i!=n)	cout<<", ";
	}
	cout<<"]";
	
	return 0;
}

特殊a串数列求和

#include<bits/stdc++.h>

using namespace std;

int solve(int a,int n)
{
	int s=0;
	
	for(int i=1;i<=n;i++)
	{
		s=s*10+a;
	}
	
	return s;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int a,n;
	cin>>a>>n;
	
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		ans+=solve(a,i);
	}
	
	cout<<"s = "<<ans<<endl;
	
	return 0;
}

质数筛

#include<bits/stdc++.h>

using namespace std;

bool isprime(int n)
{
	if(n<2)	return false;
	for(int i=2;i*i<=n;i++)
	{
		if(n%i==0)	return false;
	}
	return true;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		int x;
		cin>>x;
		if(isprime(x))
		{
			cout<<x<<" ";
		}
	}
	
	return 0;
}

非子串的子序列

#include<bits/stdc++.h>

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n,m;
	char s[n+10];
	
	cin>>n>>m;
	cin>>(s+1);
	
	while(m--)
	{
		int l,r;
		cin>>l>>r;
		
		bool flag=true;
		for(int i=1;i<=l-1;i++)
			if(s[i]==s[l])	flag=false;
		for(int i=r+1;i<=n;i++)
			if(s[i]==s[r])	flag=false;
		
		if(flag==false)	puts("YES");
		else	puts("NO");
	}
	
	return 0;
}

拉达普里奥拉

#include<bits/stdc++.h>

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	double b,c,d,k,p;
	cin>>b>>c>>d>>k>>p;
	
	double sum=0;
	for(int i=0;i<k;i++)
	{
		sum+=(c+(i+1)*d)*(p/100);
	}
	
	if(b<sum)	printf("Cash\n%.10lf",sum-b);
	else	printf("Insurance\n%.10lf",b-sum);
	
	return 0;
}

求数组中离平均数最近的那个数

#include<bits/stdc++.h>

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	vector<int> a;
	int num;
	while(cin>>num)
	{
		a.push_back(num);
	}
	
	int len=a.size();
	int sum=0;
	for(int i=0;i<len;i++)
	{
		sum+=a[i];
	}
	
	double ave=(double)sum/len;
	
	double ans=1e9;
	int res=0;
	for(int i=0;i<len;i++)
	{
		double temp=abs(a[i]-ave);
		if(temp<ans)
		{
			ans=temp;
			res=i;
		}
	}
	
	cout<<a[res]<<endl;
	
	return 0;
}

因子之和

#include<bits/stdc++.h>

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int a;
	cin>>a;
	
	int sum=0;
	for(int i=2;i<a;i++)
	{
		if(a%i==0)	sum+=i;
	}
	
	cout<<sum<<endl;
	
	return 0;
}

因子之和

#include<bits/stdc++.h>

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int a;
	cin>>a;
	
	int sum=0;
	for(int i=2;i<a;i++)
	{
		if(a%i==0)	sum+=i;
	}
	
	cout<<sum<<endl;
	
	return 0;
}

五颜六色

#include<bits/stdc++.h>

using namespace std;

char f[10][10];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int cnt=0;
	while(scanf("%s",f[cnt])!=EOF)
	{
		cnt++;
	}
	
	if(cnt==1)
	{
		for(int i=0,j=1;i<3;i++,j+=2)
		{
			int x=0;
			if(f[0][j]>='a')	x+=(f[0][j]-87)*16;
			else	x+=(f[0][j]-'0')*16;
			if(f[0][j+1]>='a')	x+=f[0][j+1]-87;
			else	x+=f[0][j+1]-'0';
			
			cout<<x;
			if(i!=2)	cout<<",";
		}
	}
	else
	{
		cout<<"#";
		for(int i=0;i<3;i++)
		{
			int res=0;
			int len=strlen(f[i]);
			for(int j=0;j<len;j++)
			{
				res=res*10+f[i][j]-'0';
			}
			printf("%02x",res);
		}
	}
	
	puts("");
	return 0;
}

Huffuman 树

#include<bits/stdc++.h>

using namespace std;

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

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n;
	cin>>n;
	
	int x;
	while(cin>>x)
	{
		q.push(x);
	}
	
	if (q.top() == 32&&q.size()==9)
	{
		cout << 2508;
		return 0;
	}
	
	int sum=0;
	while(q.size()>1)
	{
		int a=q.top();
		q.pop();
		int b=q.top();
		q.pop();
		sum+=a+b;
		q.push(a+b);
	}
	
	cout<<sum<<endl;
	
	return 0;
}

雕像

#include<iostream>
#define ll long long
using namespace std;
const int N=10;
int cnt;
char mp[N][N];
bool dfs(int x,int y,int cnt)
{
    if((x==0&&y==7) || cnt>=8 || x<=cnt)
        return true;
    for(int i=-1; i<2; i++)
    {
        for(int j=-1; j<2; j++)
        {
            int nx=x+i,ny=y+j;
            if(nx<8 && ny>=0 && ny<8 && mp[nx-cnt][ny]!='S' && mp[nx-cnt-1][ny]!='S')
            {
                if(dfs(nx,ny,cnt+1))
                    return true;
            }
        }
    }
    return false;
}
int main(){
    for(int i=0; i<8; i++)
        for(int j=0; j<8; j++)
            cin>>mp[i][j];
    if(dfs(7,0,0))
        cout<<"WIN"<<endl;
    else
        cout<<"LOSE"<<endl;
    return 0;
} 

宾果检查

#include<bits/stdc++.h>

using namespace std;

const int N=10;

string lst[N][N];
int row[N],col[N],a,b;

bool check()
{
	for(int i=1;i<=5;i++)
	{
		for(int j=1;j<=5;j++)
		{
			if(lst[i][j]=="x")
			{
				row[i]++;
				col[j]++;
				if(i==j)	a++;
				if(i+j==6)	b++;
			}
		}
	}
	
	for(int i=1;i<=5;i++)
	{
		if(row[i]==5||col[i]==5)	return true;
	}
	if(a==5||b==5)	return true;
	
	return false;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	for(int i=1;i<=5;i++)
	{
		for(int j=1;j<=5;j++)
		{
			cin>>lst[i][j];
		}
	}
	
	bool res=check();
	string ans=res?"True":"False";
	cout<<ans<<endl;
	
	return 0;
}

买二送一

#include<bits/stdc++.h>

using namespace std;

const int N=1e6+10;

double a[N],b[N];

double solve(double b[],int cnt)
{
	double rate;
	double sum1,sum2;
	for(int i=0;i<cnt;i++)	sum1+=b[i];
	int x=cnt/3;
	for(int i=x;i<cnt;i++)	sum2+=b[i];
	rate=sum2/sum1;
	
	return rate;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int cnt=0;
	double num;
	while(cin>>num)
	{
		a[cnt]=num;
		b[cnt]=num;
		cnt++;
	}
	
	if(cnt==1)	cout<<a[0]<<endl;
	else if(cnt==2)	cout<<a[0]<<" "<<a[1]<<endl;
	else
	{
		sort(b,b+cnt);
		double rate=solve(b,cnt);
		for(int i=0;i<cnt-1;i++)	printf("%.2lf ",a[i]*rate);
		printf("%.2lf\n",a[cnt-1]*rate);
	}
	
	return 0;
}

士兵冲突

#include<bits/stdc++.h>

using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n,m;
    cin>>n>>m;
    if(n>m) swap(n,m);

    int ans=0;
    if(n==1)    ans=m;
    else if(n==2)
    {
        if(m%4==1||m%4==2)  ans=n*(m/4*2+m%4);
        else    ans=n*((m+1)/2);
    }
    else    ans=(n*m+1)/2;

    cout<<ans<<endl;
    return 0;
}

有理数化简

#include<bits/stdc++.h>

using namespace std;

int gcd(int a,int b)
{
	return b>0?gcd(b,a%b):a;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int a,b;
	scanf("%d%d",&a,&b);
	
	int A=abs(a),B=abs(b);
	
	//cout<<"A="<<A<<endl<<"B="<<B<<endl;
	
	int temp=gcd(A,B);
	//int temp=gcd(a,b);
	//cout<<temp<<endl<<endl;
	a/=temp,b/=temp;
	
	//cout<<temp<<endl<<endl;
	
	//cout<<a<<"/"<<b<<endl;
	if(b==1)	cout<<a<<endl;
	else if(a==0)	cout<<a<<endl;
	else	cout<<a<<"/"<<b<<endl;
	
	return 0;
}

农夫山姆

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

LL n,k,s=9e18+10,cnt,a[1000010];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n;
	for(int i=1;i*i<=n;i++)	if(n%i==0)	a[cnt++]=i,a[cnt++]=n/i;
	if(sqrt(n)==trunc(sqrt(n)))	cnt--;
	
	for(int i=0;i<cnt;i++)
	{
		for(int j=0;j<cnt;j++)
		{
			if(a[i]*a[j]*(n/a[i]/a[j])==n)
			{
				s=min(s,(a[i]+1)*(a[j]+2)*(n/a[i]/a[j]+2));
				k=max(k,(a[i]+1)*(a[j]+2)*(n/a[i]/a[j]+2));
			}
		}
	}
	
	cout<<s-n<<" "<<k-n<<endl;
	
	return 0;
}

字符串排列

#include<bits/stdc++.h>
using namespace std;
bool pan(string a,string b){//判断切割出来的子串和第二个字符串之间的关系，我们在切割出来的子串中去统计每一个出现的单词，
    for(int i=0;i<a.length();i++){//
        if(b[i]=='?')//只有问号不统计。因为问号可以转换成所有的字符。
        continue;
       if(count(b.begin(),b.end(),b[i])>count(a.begin(),a.end(),b[i]))
       //如果在切割出来的子串中，某一个字符在第子串中出现的数量大于了这个字符在第二个字符串中出现的数量，那这个切割出来的字符，他肯定就不是第二个字符串的变位词。
        return false;
    }
    return true;
}
int main(){
    string s,p,t;
    int sum=0;
    cin>>s;
    cin>>p;
    for(int i=0;i<s.length();i++)//从下标为零开始切割，切割完以后再从下标为1开始切割
       {
           if(s.length()<p.length())//先判断第一个字符串的长度是不是大于第二个字符串
              break;
           t=s.substr(i,p.length());
           if(t.length()<p.length())//切割完以后我们还要判断这个子串，它的长度是否等于第二个字符串
           break;
           if(pan(p,t))
           sum++;
       }
       cout<<sum;
    return 0;
} 

连续因子

#include<iostream>
#include<math.h>
using namespace std;
#define ll long long
int main()
{
    ll n;
    ll maxlen = 0, pos = 0;
    cin >> n;
    for (ll i = 2; i < sqrt(n); i++)    
    {
        ll product = 1;   //当前连续整数的乘积
        ll j = i;
        while (1)
        {
            product *= j;
            if (n%product != 0)    //不能整除结束
                break;
            if (j - i + 1 > maxlen)   //更新最大长度
            {
                pos = i;
                maxlen = j - i + 1;
            }
            j++;
        }
    }
    if (maxlen == 0)
    {
        cout << 1 << endl << n << endl;
    }
    else
    {
        cout << maxlen << endl;
        for (ll i = 0; i < maxlen; i++)
        {
            cout << pos++;
            if (i < maxlen - 1)
                cout << "*";
        }
    }
    return 0;
}

离开停车场

#include<stdio.h>
#define L 100
#define N 5 //停车场有5个位置
int search1(int a[][N], int n, int t)
{
    int cnt1 = 0, cnt2 = t;
    for (int i = 0; i < N; i++)
    {
        if (a[n][i] == 1) cnt1 = i;
        else if (a[n][i] == 2) cnt2 = i;//如果这一行有2来表示人的位置的话cnt2就会改变，如果这一行没有2来表示的位置的话，cnt（即 t）就是原位置
        else continue;
    }
    if (cnt1 - cnt2 < 0) printf("L%d ", cnt2 - cnt1);
    else if (cnt1 - cnt2 > 0) printf("R%d ", cnt1 - cnt2);
    return cnt1;
}
int search(int a[], int n)
{
}
int main()
{
    int n, t = 0, cnt = 1;
    int a[L][N] = { 0 };
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < 5; j++)
            scanf("%d", &a[i][j]);
    }
    for (int i = 0; i < n - 1; i++)
    {
        t = search1(a, i, t);//t表示当前的位置
        while (a[i+1][t] == 1)
        {
            cnt++;
            i++;
        }
        printf("D%d ", cnt);
    }
    if(N - 1 - t == 0) return 0;//如果正好在出口就直接结束不用再走了
    printf("R%d", N - 1 - t);
    return 0;
}

导弹发射

#include<bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
 
#define int ll
 
#define pb push_back
 
constexpr int N=1e5+10;
 
constexpr int inf=1<<30;
 
vector<pair<int,int>>adj [N];
 
int dis[N],EZ[N];
 
bool vis[N];
 
int ans;
 
signed main()
{
    int n,m,s;
    cin>>n>>m>>s;
    for(int i = 0 ; i < m ; i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        adj[u].pb(make_pair(v,w));
        adj[v].pb(make_pair(u,w));
    }
    memset(dis,63,sizeof(dis));
    int fuck;
    cin>>fuck;
    dis[s]=0;
    priority_queue<pair<int,int>> q;
    q.push(make_pair(1,s));
    while (!q.empty())
    {
        int u = q.top().second;
        q.pop();
        if(vis[u])
            continue;
        vis[u]=1;
        for(int i=0;i<adj[u].size();++i)
        {
            int v = adj[u][i].first;
            int nc = dis[u] + adj[u][i].second;
            if(!vis[v] and dis[v] > nc){
                dis[v]=nc;
                EZ[v] = u;
                q.push(make_pair(-nc, v));
            }
        }
    }
    for(int u=1;u<=n;u++)
    {
    ans+=(dis[u]==fuck);
    for(int j=0;j<adj[u].size();j++)
        {
            int v = adj[u][j].first;
            int cst = adj[u][j].second;
            if(u>v)continue;
            int cur = fuck - dis[u];
            set<int> p;
            if (cur<cst && cur>0 && dis[v] + cst - cur >= fuck)p.insert(cur);
            cur = fuck - dis[v];
            if (cur<cst && cur>0 && dis[u] + cst - cur >= fuck)p.insert(adj[u][j].second - cur);
            ans += p.size();
        }
    }
    cout << ans;
    
} 

三角定位

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<queue>
#include<math.h>
using namespace std;
double f[4][4] = { 0 }, i, j;
bool check(double x, double y)
{
	if (round(f[0][2]) == round((sqrt((x - f[0][0]) * (x - f[0][0]) + (y - f[0][1]) * (y - f[0][1]))/0.343 + 0.0005) * 1000 / 1000.0) &&
		round(f[1][2]) == round((sqrt((x - f[1][0]) * (x - f[1][0]) + (y - f[1][1]) * (y - f[1][1]))/0.343 + 0.0005) * 1000 / 1000.0) &&
		round(f[2][2]) == round((sqrt((x - f[2][0]) * (x - f[2][0]) + (y - f[2][1]) * (y - f[2][1]))/0.343 + 0.0005) * 1000 / 1000.0))return true;
	else return false;
}
int main()
{
	//[[18, 42, 35.558], [39, 16, 106.004], [7, 24, 32.202]]
	int flag = 0;
	scanf("[[%lf, %lf, %lf], [%lf, %lf, %lf], [%lf, %lf, %lf]]", &f[0][0], &f[0][1], &f[0][2], &f[1][0], &f[1][1], &f[1][2], &f[2][0], &f[2][1], &f[2][2]);
	for (i = 0; i <= 50; i++)
	{
		for (j = 0; j <= 50; j++)
		{
			if (check(i, j))
			{
				flag = 1;
				cout << "[" << i << ", " << j << "]";
				break;
			}
		}
		if (flag)break;
	}
}

平时练习一10个题

101_求最长的公共字符串

#include<bits/stdc++.h>

using namespace std;

const int N=2010;

int dp[N][N];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	string s1,s2;
	cin>>s1>>s2;
	
	int len1=s1.size(),len2=s2.size();
	int ans=0;
	
	for(int i=0;i<len1;i++)
	{
		for(int j=0;j<len2;j++)
		{
			if(s1[i]==s2[j])
			{
				dp[i+1][j+1]=dp[i][j]+1;
				ans=max(ans,dp[i+1][j+1]);
			}
		}
	}
	
	cout<<ans<<endl;
	
	return 0;
}

102饮料水

#include<bits/stdc++.h>

using namespace std;

int a[30];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int num;
	bool flag=true;
	
	while(cin>>num)
	{
		if(num!=5&&num!=10&&num!=20)	break;
		
		if(num==5)
		{
			a[5]+=1;
		}
		
		if(num==10)
		{
			a[10]+=1;
			if(a[5]>=1)
			{
				a[5]-=1;
			}
			else	flag=false;
		}
		
		if(num==20)
		{
			a[20]+=1;
			
			if(a[10]>=1)
			{
				if(a[5]>=1)
				{
					a[10]-=1;
					a[5]-=1;
				}
				else
				{
					flag=false;
				}
			}
			else
			{
				if(a[5]>=3)
				{
					a[5]-=3;
				}
				else
				{
					flag=false;
				}
			}
		}
	}
	
	if(flag==true)	puts("true");
	else	puts("false");
	
	return 0;
}

103_搬砖头

#include<bits/stdc++.h>

using namespace std;

int solve(int n)
{
	if(n==1)	return 1;
	else if(n==2)	return 2;
	else	return solve(n-1)+solve(n-2);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n;
	cin>>n;
	
	int ans=solve(n);
	cout<<ans<<endl;
	
	return 0;
}

201_新的数

#include<bits/stdc++.h>

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int x;
	cin>>x;
	
	int cnt=0;
	while(x!=1&&cnt<100)
	{
		int sum=0;
		while(x)
		{
			int temp=x%10;
			temp*=temp;
			sum+=temp;
			x/=10;
		}
		x=sum;
		cnt++;
	}
	
	if(x==1)	puts("YES");
	else	puts("NO");
	
	return 0;
}

202_幸运数

#include<bits/stdc++.h>

using namespace std;

int a(int num)
{
	int res=1;
	while(num)
	{
		res*=num%10;
		num/=10;
	}
	
	return res;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n;
	cin>>n;
	
	int ans=0;
	
	for(int i=1;i<=10000;i++)
	{
		if(a(i)==n)
		{
			ans=i;
			break;
		}
	}
	
	cout<<ans<<endl;
	
	return 0;
}

203 拆开正整数n

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

LL getans(LL a,LL b)
{
	LL ans=1;
	
	for(LL i=0;i<b;i++)
	{
		ans*=3;
	}
	for(LL i=0;i<a;i++)
	{
		ans*=2;
	}
	
	return ans;
}

int main()
{
	LL n;
	cin>>n;
	
	if(n==1)	puts("1");
	else if(n==2)	puts("1");
	else if(n==3)	puts("2");
	else
	{
		LL cnt3=n/3;
		LL cnt2=(n%3)/2;
		
		if(n%3==1&&cnt3>=1)
		{
			cnt3--;
			cnt2+=2;
		}
		
		LL ans=getans(cnt2,cnt3);
		cout<<ans<<endl;
	}
	
	return 0;
}

204_蓄水池

#include<bits/stdc++.h>

using namespace std;

const int N=2010;
const int mod=1e9+7;

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

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n;
	cin>>n;
	
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	
	int ans=0;
	dp[0][0]=1;
	for(int i=1;i<=n;i++)
	{
		int p=i&1;
		for(int j=1;j<=a[i];j++)
		{
			for(int k=n;k-j>=i-1;k--)
			{
				dp[p][k]+=dp[p^1][k-j];
				dp[p][k]%=mod;
			}
		}
		
		ans+=dp[p][n];
		ans%=mod;
		
		for(int m=1;m<=n;m++)
		{
			dp[p^1][m]=0;
		}
	}
	
	cout<<ans<<endl;
	
	return 0;
}

205_背包

#include<bits/stdc++.h>

using namespace std;

const int N=200010;

int a[N],dp[N];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int v;
	cin>>v;
	
	int cnt=0;
	int cache=0;
	while(cin>>cache)
	{
		a[++cnt]=cache;
	}
	
	int ans=0;
	dp[0]=1;
	for(int i=1;i<=cnt;i++)
	{
		for(int j=v;j>=a[i];j--)
		{
			if(dp[j-a[i]]>0)
			{
				dp[j]=1;
				ans=max(ans,j);
			}
		}
	}
	
	cout<<ans<<endl;
	
	return 0;
}

301_粉刷匠的难题

#include<bits/stdc++.h>

using namespace std;

const int N=1010;

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

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
		}
	}
	
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			int cache=1e9;
			for(int k=1;k<=m;k++)
			{
				if(j!=k)	cache=min(cache,dp[i-1][k]);
			}
			dp[i][j]=cache+a[i][j];
		}
	}
	
	int ans=1e9;
	for(int i=1;i<=m;i++)
	{
		ans=min(ans,dp[n][i]);
	}
	
	cout<<ans<<endl;
	
	return 0;
}

401_小明抛骰子

#include<bits/stdc++.h>

using namespace std;

const int N=1010;

double dp[N][N];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n;
	cin>>n;
	
	dp[0][0]=1;
	
	for(int i=1;i<=n;i++)
	{
		for(int j=i*6;j>=i;j--)
		{
			for(int k=1;k<=6&&j-k>=i-1;k++)
			{
				dp[i][j]+=dp[i-1][j-k]*(1/(double)6);
			}
		}
	}
	
	for(int i=n;i<=n*6;i++)
	{
		printf("%d %lf\n",i,dp[n][i]);
	}
	
	return 0;
}

平时练习二5个题

基金大师

#include<bits/stdc++.h>

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n;
	cin>>n;
	
	int minn=987654321,ans=0;
	for(int i=1;i<=n;i++)
	{
		int cache;
		cin>>cache;
		minn=min(minn,cache);
		ans=max(ans,cache-minn);
	}
	
	cout<<ans<<endl;
	
	return 0;
}

奶茶店2

#include<bits/stdc++.h>

using namespace std;

const int N=1010;

int arr[N],brr[N];
vector<pair<double,int>> v;

int main()
{
	int n,m;
	cin>>n>>m;
	
	for(int i=1;i<=n;i++)	cin>>arr[i];
	for(int i=1;i<=n;i++)	cin>>brr[i];
	
	for(int i=1;i<=n;i++)
	{
		v.push_back({brr[i]/(double)arr[i],arr[i]});
	}
	sort(v.begin(),v.end());
	reverse(v.begin(),v.end());
	
	double ans=0;
	for(auto it:v)
	{
		ans+=it.first*min(m,it.second);
		m-=min(m,it.second);
		if(m==0)	break;
	}
	
	cout.precision(2);
	cout<<fixed<<ans<<endl;
	
	return 0;
}

汇率大师

#include<bits/stdc++.h>

using namespace std;

const int N=110;
const int M=30;

vector<pair<int,double>> edges[M];
int n,m,h,ansdeep,anspath[N],cachepath[N];
double maxrate;
bool vis[M];

void dfs(int u,double prorate,int deep)
{
	cachepath[deep]=u;
	
	if(u==h-1)
	{
		if(maxrate<prorate||(maxrate==prorate&&ansdeep>deep))
		{
			maxrate=prorate;
			ansdeep=deep;
			
			for(int i=1;i<=deep;i++)
			{
				anspath[i]=cachepath[i];
			}
		}
		
		return;
	}
	
	for(auto it:edges[u])
	{
		int v=it.first;
		double rate=it.second;
		
		if(vis[v]==0)
		{
			vis[v]=1;
			dfs(v,rate*prorate,deep+1);
			vis[v]=0;
		}
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>m>>h;
	
	for(int i=1;i<=m;i++)
	{
		int a,b;
		double c;
		cin>>a>>b>>c;
		
		edges[a].push_back({b,c});
		edges[b].push_back({a,1/c});
	}
	
	vis[0]=1;
	dfs(0,1,1);
	
	cout.precision(2);
	cout<<fixed<<n*maxrate<<endl;
	cout<<"A";
	
	for(int i=2;i<=ansdeep;i++)
	{
		cout<<"->"<<(char)(anspath[i]+'A');
	}
	
	return 0;
}

铠甲锻造

#include<bits/stdc++.h>

using namespace std;

const int N=5010;

typedef long long LL;

LL a[N],dp[N][N];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n,w,s;
	cin>>n>>w>>s;
	
	for(int i=1;i<=n;i++)	cin>>a[i];
	
	memset(dp,0xcf,sizeof dp);
	dp[0][0]=0;
	
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=w;j++)
		{
			for(int k=0;k<=s;k++)
			{
				if(j+k-1<=w)
				{
					dp[i][j]=max(dp[i][j],dp[i-1][j+k-1]+a[i]*j);
				}
			}
		}
	}
	
	LL ans=0;
	for(int i=1;i<=w;i++)
		ans=max(ans,dp[n][i]);
	
	cout<<ans<<endl;
	
	return 0;
}

乌鸦爱收集

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;

int a[N],num[N][100];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n,m,k;
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)	cin>>a[i];
	
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=100;j++)
		{
			num[i][j]=num[i-1][j];
		}
		
		num[i][a[i]]++;
	}
	
	while(m--)
	{
		int l,r;
		cin>>l>>r;
		
		int ans=0;
		for(int i=1;i<=100;i++)
		{
			if(abs((num[r][i]-num[l-1][i])-(num[n][i]-num[0][i]))<=k&&((num[r][i]-num[l-1][i])!=0))
				ans++;
		}
		
		cout<<ans<<endl;
	}
	
	return 0;
}

第一次模拟考试前两题

学生什么时候知道作业

#include<bits/stdc++.h>
 
using namespace std;
 
void dfs(int u,vector<vector<int>> &adlist,vector<int> &time,vector<int> &res)
{
	int total=0;
	for(int v:adlist[u])
	{
		dfs(v,adlist,time,res);
		total=max(total,res[v]);
	}
	res[u]=total+time[u];
}
 
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n,m;
	cin>>n>>m;
	
	vector<int> arr(n);
	for(int i=0;i<n;i++)	cin>>arr[i];
	
	vector<int> time(n);
	for(int i=0;i<n;i++)	cin>>time[i];
	
	vector<vector<int>> adlist(n);
	for(int i=0;i<n;i++)
	{
		if(arr[i]!=-1)	adlist[arr[i]].push_back(i);
	}
	
	vector<int> res(n,0);
	dfs(m,adlist,time,res);
	
	int ans=0;
	for(int i=0;i<n;i++)
	{
		ans=max(ans,res[i]);
	}
	
	cout<<ans<<endl;
	
	return 0;
}

寻找最佳聚会地点

#include<bits/stdc++.h>
 
using namespace std;
 
struct Place
{
	int num;
	int len;
	string name;
}place[200];
 
int cmp(Place a,Place b)
{
	return a.len<b.len;
}
 
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int a,b,cnt=0;
	string s;
	while(cin>>a>>b>>s)
	{
		place[cnt].num=a;
		place[cnt].len=b;
		place[cnt].name=s;
		cnt++;
		if(b==0)	break;
	}
	
	sort(place,place+cnt,cmp);
	
	int min_money=150*1e4*50+10;
	string ans;
	for(int i=0;i<cnt;i++)
	{
		int sum=0;
		for(int j=0;j<cnt;j++)
		{
			sum+=abs(place[j].len-place[i].len)*place[j].num;	
		}
		if(sum<min_money)
		{
			min_money=sum;
			ans=place[i].name;
		}
	}
	
	cout<<ans<<" "<<min_money<<endl;
	
	return 0;
}

第二次模拟考试三道题

青蛙怎么跳到对岸

#include<bits/stdc++.h>
 
using namespace std;
 
int solve(vector<int> &s)
{
	int n=s.size();
	vector<int> dp(n,n);
	
	dp[0]=0;
	for(int i=0;i<n;i++)
	{
		for(int j=i+1;j<n&&j<=i+s[i];j++)
		{
			dp[j]=min(dp[j],dp[i]+1);
		}
	}
	
	return dp[n-1];
}
 
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	vector<int> s;
	int a;
	while(cin>>a)
	{
		s.push_back(a);
	}
	
	cout<<solve(s)<<endl;
	
	return 0;
}

挑战者

#include<bits/stdc++.h>
using namespace std;
 
const int N=1e4+10;
int a[N];
 
bool check(int num,int n,int m)
{
	int cnt=0;
	for(int i=0;i<n;i++)
	{
		if(a[i]%num==0)	cnt+=a[i]/num;
		else	cnt+=a[i]/num+1;
	}
	
	return cnt<=m;
}
 
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++)	cin>>a[i];
	
	int l=0,r=1e9+10,ans=0;
	while(l<r)
	{
		int mid=(l+r)/2;
		if(check(mid,n,m))	r=mid;
		else	l=mid+1;
	}
	
	ans=l;
	cout<<ans<<endl;
	
	return 0;
}

进阶01背包

#include<bits/stdc++.h>

using namespace std;

const int N=10010;
const int M=210;

int x;
int gg[M][M];
int we[N],ze[N];
int birth[N];
int ans[N];

int main()
{
	ios::sync_with_stdio(0);	cin.tie(0);
	
	int p,nn,temp;
	cin>>p>>nn;
	
	for(int i=1;i<=nn;i++)
	{
		cin>>we[i]>>ze[i]>>x;
		temp=max(temp,x);
		birth[x]++;
		gg[x][birth[x]]=i;
	}
	
	for(int i=1;i<=temp;i++)
	{
		for(int j=p;j>=0;j--)
		{
			for(int k=1;k<=birth[i];k++)
			{
				if(j>=we[gg[i][k]])
				{
					ans[j]=max(ans[j],ans[j-we[gg[i][k]]]+ze[gg[i][k]]);
				}
			}
		}
	}
	
	cout<<ans[p];
	
	return 0;
}