T1 加 (add)

题目描述

你有一个变量x，一开始为0。

你还有n种操作，第i种操作可以进行至多ki次，每次可以让x变为min(x+ai,hi)。

求x最大能变到多少。

输入格式

第一行一个正整数n。

接下来n行，每行三个正整数，表示ai,hi,ki。

输出格式

输出一个整数，表示答案。

样例

样例输入

78 35 15 35 115 35 18 35 110 35 14 35 12 35 1

样例输出

35

数据范围

​ 对于 40%的数据，? ≤ 10，?? = 1，ℎ? ≤ 100且所有ℎ?相等。

​ 对于 100%的数据，? ≤ 100,?? ≤ 30，ℎ? ≤ 104，?? ≤ 200。

附加说明

​ 如果你觉得太简单，可以把这题的数据范围当成：

​ ? ≤ 106，??,ℎ?,?? ≤ 1018。

Solution

显然h小的先做更优，排序后模拟即可

把每种操作看成x=min(x+a*k,h)，注意判\(a\ *\ k\)爆long long的情况，由于文件较大需要用fread优化

#include
    
     #include
     
      #include
      
       #define ll long longusing namespace std;char B[1<<26],*S=B;inline ll read(){    ll x;char c;    while((c=*S++)<'0'||c>'9');    for(x=c-'0';(c=*S++)>='0'&&c<='9';)x=x*10+c-'0';    return x;}#define MN 1000005long long n,a[MN],h[MN],k[MN],id[MN];bool cmp(const long long&x,const long long&y){return h[x]
       
        2e18) now=h[id[i]];        else now=min(now+a[id[i]]*k[id[i]],h[id[i]]);    printf("%lld\n",now);    return 0;}
       
      
     
    

T2 减(minus)

问题描述

S 君是秘密组织“TB”的成员，现在他要执行一项潜入任务。潜入地点可以抽象为一张?个点?条边的无向

图，点编号为1到?，每条边上设有警戒设备，第?条边上的警戒值为??，警戒值越高代表经过这条边时越危

险。现在 S 君已经位于1号节点，他需要到位于?号节点的数据库上窃取数据。

为了 S 君的安全，S 君的搭档小 N 会在后方提供支援，小 N可以让至多?条边上的警戒设备在这次潜入任

务中暂时失效。小N 的目标是让 S 君执行任务时需要经过的最危险的有效警戒设备的警戒值尽可能小，请你

求出这个值。

输入格式

第一行三个整数?,?,?。 接下来?行，每行三个整数??,??,??，表示有一条连接??,??且

警戒值为??的边。

输出格式

输出一个整数，表示答案，如果不能完成任务，输出−1，如果可以不经过任何有效警戒设备，输出0。

样例

样例输入

5 7 1 1 2 5 3 1 4 2 4 8 3 2 3 5 2 9 3 4 7 4 5 6

样例输出

4

数据范围

对于全部数据， ? ≤ 1000， 0 ≤ ? ≤ ? ≤ 104， 1 ≤ ?? ≤ 106。数据可能有一定梯度。

附加说明

如果你觉得太简单，可以把这题的数据范围当成：

?,? ≤ 106，? ≤ ?，1 ≤ ?? ≤ 109。

Solution

二分答案后用最短路求1到n最少经过多少条大于答案的边，不超过k即合法。要求的最短路边权只有0和1，

可以直接bfs，走长度为0的边拓展出的点直接放在队头优先拓展，答案只要二分是第几大的边权，时间复杂

度O((n+m)logm)

#include
    
     #include
     
      #include
      
       #include
       
        char B[1<<26],*S=B;inline int read(){    int x;char c;    while((c=*S++)<'0'||c>'9');    for(x=c-'0';(c=*S++)>='0'&&c<='9';)x=x*10+c-'0';    return x;}#define MM 1000005#define MN 1000005#define mid (l+r>>1) int n,m,k;struct edge{int to,w,nex;}e[MM<<1];int cnt,hr[MN];int id[MM],W[MM<<1],MAXW;inline void ins(int x,int y,int w){    e[++cnt]=(edge){y,1,hr[x]};hr[x]=cnt;W[cnt]=w;    e[++cnt]=(edge){x,1,hr[y]};hr[y]=cnt;W[cnt]=w;    id[cnt>>1]=cnt;}int d[MN],q[MM<<1],hq,tq;bool mark[MN];inline void bfs(){    memset(d,127,sizeof d);    memset(mark,false,sizeof mark);register int i;    for(d[q[hq=tq=MN]=1]=0;hq<=tq;hq++)if(!mark[q[hq]]){        mark[q[hq]]=true;int D=d[q[hq]];if(D>k) break;        for(i=hr[q[hq]];i;i=e[i].nex)if(!mark[e[i].to]&&d[e[i].to]>D+e[i].w){            if(e[i].w==1) d[q[++tq]=e[i].to]=D+1;            else d[q[hq--]=e[i].to]=D;        }    }   }bool check(int x){    register int i;    for(i=1;i<=cnt;i++) e[i].w=W[i]>x?1:0;    bfs();return d[n]<=k; }inline bool cmp(const int&x,const int&y){    return W[x]
        
         m) return 0*puts("-1");    if(r<1) return 0*puts("0");     printf("%d\n",W[id[ans]]);    return 0;}
        
       
      
     
    

T3 乘(product)

问题描述

求有多少个?位数各位数字的乘积为?。

这里的?位数字可以有前导0,但前导0同样算入乘积中。

输入格式

一行两个整数?,?。

输出格式

输出一个整数，表示答案。

样例

样例输入

2 0

样例输出

19

数据范围

对于 20%的数据，? ≤ 6。

对于 50%的数据，? ≤ 16。

另有 30%的数据，? = 0。

对于 100%的数据，1 ≤ ? ≤ 50,0 ≤ ? ≤ 109。

附加说明

如果你觉得太简单，可以把这题的数据范围当成：1 ≤ ? ≤ 50,0 ≤ ? ≤ 1018。

Solution

1. k=0直接枚举第一个0的出现位置，在此之前必须是1~9，在此之后可以是0~9，高精度算一下就好了

2. k>0时预处理k的所有因数，\(f_{i,j}\)表示前i位乘积为第j种因数的方案数，转移可以预处理一下每种因数乘上

   1~9会变成哪种因数，考虑2，3，5，7四种质因子，10^18内只由这四种质因子组成的最多因数的数也只有

   7680个，所以可以轻松AC

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
       
      
     
    

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！