[2020년 바이두의 별·프로그래밍 대회 - 1차전2] 코다의 문제집

진짜 한 문제만 2차전에 들어가지.
Poker
시뮬레이션 문제에 서명하다.주의는 회수한 돈을 아래로 가져가는 것이다. 만약 당신이 직접 돈의 소모량을 계산한다면, 위로 가져가야 한다.

#include
using namespace std;
int t,n,m,p,ans,re;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>t;
    while(t--)
    {
        ans=0;
        cin>>n>>m>>p;
        p=100-p;
        while(n>=m)
        {
            re=m*p/100;
            n=n-m+re;
            ans++;
        }
        cout<<ans<<endl;
    }
}

Distance
제목이 허황하게 정해져 있다. 친구가 모두 같은 방향의 직선에 있을 때 거리는 가장 짧다.

#include
#define int long long
using namespace std;
const int maxn=1e5+7;
int t,n,a[maxn],ans;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>t;
    while(t--)
    {
        ans=0;
        cin>>n;
        for(int i=1;i<=n;++i)
            cin>>a[i];
        sort(a+1,a+n+1);
        for(int i=1;i<n;++i)
            ans+=i*(n-i)*(a[i+1]-a[i]);
        cout<<ans<<endl;
    }
}

Covid
건도g, 시간마다 장소마다 저장하는 사람.그림p를 작성하여 모든 사람의 행동 궤적을 저장한다.그리고 샅샅이 뒤져 표시를 해라.

#include
#define int long long
using namespace std;
typedef pair<int,int> P;
const int maxn=2e4+1;
vector<int> g[101][11];
vector<P> p[maxn];
int t,n,len,u,v,vir[maxn],vis[101][11];
void dfs(int tt,int pp)
{
    for(auto ppp:g[tt][pp])
    {
        vir[ppp]=1;
        for(auto path:p[ppp])
        {
            if(!vis[path.first][path.second]&&path.first>tt)
            {
                vis[path.first][path.second]=1;
                dfs(path.first,path.second);
            }
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>t;
    for(int cas=1;cas<=t;++cas)
    {
        memset(vis,0,sizeof(vis));
        memset(vir,0,sizeof(vir));
        for(int i=1;i<=n;++i)
            p[i].clear();
        for(int i=1;i<=100;++i)
            for(int j=1;j<=10;++j)
                g[i][j].clear();
        cin>>n;
        for(int i=1;i<=n;++i)
        {
            cin>>len;
            for(int j=1;j<=len;++j)
            {
                cin>>u>>v;
                g[u][v].push_back(i);
                p[i].push_back(make_pair(u,v));
            }
        }
        for(auto pp:p[1])
        {
            if(!g[pp.first][pp.second].empty())
                dfs(pp.first,pp.second);
        }
        int first=1;
        for(int i=1;i<=n;++i)
            if(vir[i])
            {
                if(first)
                {
                    cout<<i;
                    first=0;
                }
                else
                {
                    cout<<" "<<i;
                }
            }
        cout<<endl;
    }
}

Car
폭수, 최적화, 카드 시한.줄의 최소를 제한하지 않는 최대치를 구하려면 줄의 최소를 먼저 구한 다음에 n으로 그것을 빼면 된다.물론 이 문제의 표정은 2점 답이어야 하지만, 나는 게으르다.

#include
using namespace std;
int t,n,x,cnt[12],sum[12],ans;
inline int redn()
{
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
void dfs(int num)
{
    if(num==10)
    {
        ans=max(ans,*min_element(sum,sum+5));
        return;
    }
    for(int i=0;i<5;++i)
    {
        sum[i]+=cnt[num];
        dfs(num+1);
        sum[i]-=cnt[num];
    }
}
signed main()
{
    t=redn();
    while(t--)
    {
        memset(cnt,0,sizeof(cnt));
        memset(sum,0,sizeof(sum));
        ans=0;
        n=redn();
        for(int i=1;i<=n;++i)
        {
            scanf("%d",&x);
            ++cnt[x%10];
        }
        dfs(0);
        printf("%d
",n-ans);
    }
}

Drink
첫 번째 시합의 그 모스쿠토와 차이가 많지 않지만, 이번에는 최대 비용의 최대 흐름이며, 여전히 판자를 빌려 고친 것이다.취향의 조합은 총 6가지로 n명을 6가지 취향상태로 압축하고 cnt마다 몇 명인지.원점 S에서 각 상태로 용량을 연결하는 것은 이 상태의 인원수이고 비용은 0의 변이다. 그리고 각 상태에서 세 가지 음료로 용량이 무한하다. 비용은 상태와 대응하는 음료의 즐거움값이다. 마지막으로 세 가지 음료에서 T로 용량을 연결하는 것은 이 음료의 개수이고 비용은 0의 변이다.위에서 수정한 후에 처음에 코스트를 모두 0으로 설정했다. 가장 큰 비용이기 때문에 SPFA의 조건을 코스트[e.to]로 바꿨다. 마지막으로 나는 원점 S의 아웃사이드와 송금점 T의 아웃사이드를 0에서 1로 바꿨다. 왜냐하면 하나의 확장로는 S의 아웃사이드와 T의 아웃사이드를 한 번만 지나기 때문이다. 수정한 후에 모든 비용을 통계할 때 이 두 가지 이상의 비용을 빼면 된다.

#include
const int MAXN=1e5+7;
const int inf=0x3f3f3f3f;
using namespace std;
int ls[][3]={{0,0,0},{3,2,1},{3,1,2},{2,3,1},{1,3,2},{2,1,3},{1,2,3}};
bool vis[MAXN];
int n, m, s, t;
int u, v, c, w;
int cost[MAXN], pre[MAXN], last[MAXN], flow[MAXN];
int maxFlow, minCost;
struct Edge
{
	int from, to, flow, cost;
}edge[MAXN];
int head[MAXN], num_edge;
queue <int> q;
void addedge(int from, int to, int flow, int cost)
{
	edge[++num_edge].from = head[from];
	edge[num_edge].to = to;
	edge[num_edge].flow = flow;
	edge[num_edge].cost = cost;
	head[from] = num_edge;

	edge[++num_edge].from = head[to];
	edge[num_edge].to = from;
	edge[num_edge].flow = 0;
	edge[num_edge].cost = -cost;
	head[to] = num_edge;

}
bool SPFA(int s, int t)
{
	memset(cost, 0, sizeof(cost));
	memset(flow, 0x7f, sizeof(flow));
	memset(vis, 0, sizeof(vis));
	q.push(s); vis[s] = 1; cost[s] = 0; pre[t] = -1;
	while (!q.empty())
	{
		int now = q.front();
		q.pop();
		vis[now] = 0;
		for (int i = head[now]; i != -1; i = edge[i].from)
		{
			if (edge[i].flow>0 && cost[edge[i].to]<cost[now] + edge[i].cost)
			{
				cost[edge[i].to] = cost[now] + edge[i].cost;
				pre[edge[i].to] = now;
				last[edge[i].to] = i;
				flow[edge[i].to] = min(flow[now], edge[i].flow);
				if (!vis[edge[i].to])
				{
					vis[edge[i].to] = 1;
					q.push(edge[i].to);
				}
			}
		}
	}
	return pre[t] != -1;
}
void MCMF()
{
	while (SPFA(s, t))
	{
		int now = t;
		maxFlow += flow[t];
		minCost += flow[t] * (cost[t]-2);
		while (now != s)
		{
			edge[last[now]].flow -= flow[t];
			edge[last[now] ^ 1].flow += flow[t];
			now = pre[now];
		}
	}
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int cas,nn,a,b,c;
    cin>>cas;
    while(cas--)
    {
        maxFlow=minCost=0;
        memset(head, -1, sizeof(head)); num_edge = -1;
        cin>>nn>>a>>b>>c;
        int cnt[10]={0};
        string ss;
        for(int i=1;i<=nn;++i)
        {
            cin>>ss;
            if(ss=="012") ++cnt[1];
            if(ss=="021") ++cnt[2];
            if(ss=="102") ++cnt[3];
            if(ss=="120") ++cnt[4];
            if(ss=="201") ++cnt[5];
            if(ss=="210") ++cnt[6];
        }
        n=11,m=27,s=0,t=10;
        for(int i=1;i<=6;++i)
            if(cnt[i])
            {
                addedge(0,i,cnt[i],1);
                addedge(i,7,inf,ls[i][0]);
                addedge(i,8,inf,ls[i][1]);
                addedge(i,9,inf,ls[i][2]);
            }
        addedge(7,10,a,1);
        addedge(8,10,b,1);
        addedge(9,10,c,1);
        MCMF();
        cout<<minCost<<endl;
    }
}

Cloth
똥문제는 밤새 뛰었지만 결과가 나오지 않아 포기했다.다른 사람의 코드를 붙여라.https://blog.csdn.net/a_forever_dream/article/details/107743001

#include 
using namespace std;
int T;
double a,b,x;
int main()
{
    scanf("%d",&T);while(T--)
    {
        scanf("%lf %lf %lf",&a,&b,&x);
        if(x>b)
        {
            double c=sqrt(x*x-b*b);
            if(2*c<x){
                int k=floor(a/x);int ans=2*k+1;
                double X=a-k*x,Y=X-(x-c);
                if(X>=c)ans++,Y=X-c;
                if(sqrt(x*x-X*X)+sqrt(x*x-Y*Y)<=b)ans++;
                printf("%d
",ans);
            }
            else printf("%d
",(int)(a/c)+1);
        }
        else
        {
            int ans1,ans2;
            ans1=(int)(a/x)+1;
            double c=a-1.0*(ans1-1)*x;
            c=sqrt((double)(x*x-c*c));
            if(b-c*2>=x)ans2=(int)((b-c*2-x)/x)+2;
            else if(b-c*2>=0)ans2=1;
            else ans2=0;
            printf("%d
",ans1*2+ans2);
        }
    }
}

Solo
DP, 가장 좋은 전략 중 Alice는 Bob의 매 초를 낭비할 방법을 강구해야 한다. 즉, 만약에 Alice가 Bob 앞에서 어떤 언급을 완성할 수 있다면 반드시 Bob이 풀 수 있는 순간에 제출하고 앞당겨 문제를 풀지 않도록 Bob가 이 문제를 건너뛰게 할 것이다.Bob은 건너뛰지 않기 때문에 매 문제를 완성하는 시간은 고정되어 있고, 그룹 b에 대해 접두사와 접두사를 하면 된다.앨리스는 i번까지 j로 점수를 매겼고, 최소 사용 시간은 얼마였는지 f[i][j]로 기록했다.Alice가 Bob 이전에 i번을 풀 수 있다면f[i][j]=min(f[i-1][j],f[i-1][j-1]+a[i]), 그렇지 않으면f[i][j]=f[i-1][j].f는 시간을 저장하고 제목의 시간은 최대 1e18에 달하며, inf는 0x3f3f3f3f3f를 사용하면 WA를 할 수 있음을 정의하십시오.

#include
#define int long long
using namespace std;
const int maxn=2010;
const int inf=1e18+7;
int n,a[maxn]= {0},b[maxn]= {0},f[maxn][maxn]= {0};
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int cas;
    cin>>cas;
    while(cas--)
    {
        cin>>n;
        for(int i=1; i<=n; ++i)
            cin>>a[i];
        for(int i=1; i<=n; ++i)
        {
            cin>>b[i];
            b[i]+=b[i-1];
        }
        for(int i=0; i<=n; ++i)
            for(int j=0; j<=n; ++j)
                f[i][j]=inf;
        f[0][0]=0;
        for(int i=1; i<=n; ++i)
            for(int j=0; j<=i; ++j)
                if(!j||f[i-1][j-1]+a[i]>b[i])
                    f[i][j]=f[i-1][j];
                else
                    f[i][j]=min(f[i-1][j],f[i-1][j-1]+a[i]);
        for(int i=n; i>=1; --i)
            if(f[n][i]!=inf)
            {
                cout<<i<<endl;
                break;
            }
    }
}

Hanoi

0 AC，   。