JXNU软件学院劳动教育之第一届图灵杯程序设计

A.

题意：给你一个数n；问他是否有一个奇数的公因子。
思路：除了质数2，其他的质数都是奇数。我么可以直接判断n是否为2的次幂就行。签到，当时看错了题意，真***。
代码：

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

int a[100010];
int main(){
    long long  n;
    while(cin&gt;&gt;n){
        int flag=0;
        for(int i=1;i&lt;=64;i++){
            if(n==pow(2,i)) flag=1;
        }
        if(!flag) puts("YES");
        else puts("NO");
    }
    return 0;
}

B.

思路：理解题意我们可以知道将每个人的硬币排序以后，最多硬币的那个人一定可以取得游戏的胜利，再往前推，倒数第二个如果要去的胜利的话，那他应该满足什么条件，可以发现，倒数第二个人往前的他可以得到他前面所有人的硬币归自己所有，如果他要取得胜利那么他应该大于他后面那个人的硬币数量。再往前推也类似，所以只需要对所有人的硬币数量记录位置排序，并且做一个前缀和，如果 $图片说明$ ,那么这个i位置往前都不可能在赢得游戏的胜利。记录下这个位置，输出往后的序号pos即可。（记得最终答案排序）
代码：

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

const int N=100010;
struct node{
    int num,pos;
    int sum;
}a[N];
int ans[N];
bool cmp(node a,node b){
    return a.num<b.num;
}

int n;
int main(){
    while(cin>>n){
        for(int i=1;i<=n;i++) {
            cin>>a[i].num;
            a[i].pos=i;
        }
        sort(a+1,a+1+n,cmp);
        for(int i=1;i<=n;i++){
            a[i].sum=a[i-1].sum+a[i].num;
            //sum[i]=s[i-1]+a[i].num;
        }
        int res=1;
        for(int i=2;i<n;i++){
            if(a[i-1].sum<a[i].num) res=i;
        }
        int cnt=0;
        for(int i=res;i<=n;i++){
            ans[cnt++]=a[i].pos;
        }
        sort(ans,ans+cnt);
        cout<<cnt<<endl;
        for(int i=0;i<cnt;i++){
            cout<<ans[i]<<" ";
        }
        cout<<endl;
    }
}

c

思路：二分答案，猜一个答案看他是否满足题意。那么重点就在于check函数怎么写了。 1. 首先如果mid小于有一天的货物数量，肯定是不行的。 2.我们只需要模拟他每天工作的量，看看是需要几天，用day记录用的天数。 3.如果day<="k;那么true，否则false；"

代码：

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

typedef long long ll;
typedef unsigned long long ull; 

#define sc(n) scanf("%d",&n)
#define pr(n) printf("%d\n",n)
#define endl "\n";
#define ios ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)

inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
const int N=10000010;
const int MOD = 1e9 + 7;
const int INF=1e9;
const double eps=1e-5;
ll n,m,k,d;
string s;
int a[N];

bool check(int mid){
    int day=1,su=0;
    for(int i=1;i<=n;i++){
        su+=a[i];
        if(a[i]>mid) return false;
        if(su>mid) {
            day++;
            su=a[i];
        }
    }
    if(day<=d) return true;
    else return false;
}
int main(){
    while(cin>>n>>d){
        int sum=0;
        int l=1e9;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
        l=min(l,a[i]);
    }
    int r=sum;
    int ans=0;
    while(l<=r){
        int mid=(l+r)>>1;
         //cout<<"mid="<<mid<<endl;
         if(check(mid)) ans=mid, r=mid-1;
         else l=mid+1;     
    }
    cout<<ans<<endl;
    }
    return 0;
}

d

思路：根据题目意思，首冲的奖励只有一次，而且得到的石子数量和金额是十倍的关系，那么我们就应该想怎样可以使不超过n元，得到最多的首充奖励，每一次首冲奖励只能选择一次，那么这个问题不就变成了01背包问题。首冲奖励+n*10就是最后的答案。代码：

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

int f[2020][2020];

int v[]={0, 1, 6, 28, 88, 198, 328, 648};
int w[]={0, 8, 18, 28, 58, 128, 198, 388};

int main(){
    int t,n;
    cin>>t;
    while(t--){
         cin>>n;
        for(int i=1;i<=7;i++){
            for(int j=0;j<=n;j++){
                if(j<v[i]) f[i][j]=f[i-1][j];
                else f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);
            }
        }
//        cout<<f[7][n]<<endl;
        long long ans=f[7][n]+n*10;
        cout<<ans<<endl;
    }
}