JS's Blog
0%

Posted on Edited on In ,

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=1078

题目大意：
有一只老鼠，起始点在(0,0)，起始获得一个权值，每次可以水平或垂直的至多走k步，获得该处的权值，且每次获得的权值必须比上一次的大，求最大能获得的总权值是多少

分析：
起点固定在(0,0),所以可以选dp[0][0]为dp终点，一开始以为是两点之间曼哈顿距离在k之内可达，后面一直WA，看了题解发现是题意读错了，只能上下或者左右走k步，所以结构体保存行列和权值信息，然后按权值从大到小，权值较大的先遍历，dp[i][j]表示以矩阵中(i,j)位置为起点能获得的最大权值和，dp转移式是

dp[i][j]=max⁡(max⁡p=j−kp≤j+k(dp[i][p]),max⁡q=i−kq≤i+k(dp[q][j]))+a[i][j]dp[i][j] = \max(\max_{p=j-k}^{p\leq j+k} (dp[i][p]),\max_{q=i-k}^{q\leq i+k}(dp[q][j]) )+a[i][j]

最后dp[0][0]dp[0][0]即是答案

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;

typedef long long ll;
const int maxn = 1020000;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int n,k;
int mat[120][120];
int dp[120][120];


struct Node{
    int v,r,c;
    bool operator < (const Node a)
    {
        return v>a.v;
    }
}arr[12000];


bool check(int i ,int j)
{
    if (i<1||i>n||j<1||j>n)
        return false;
    else
        return true;
}


int main()
{
    int t = 1 ;
    while (~scanf("%d%d",&n,&k))
    {
        if (n==-1&&k==-1)
            break;
        for (int i = 1;  i <= n ; i ++)
        {
            for (int j = 1 ; j <= n ; j ++)
            {
                scanf("%d",&mat[i][j]);
                dp[i][j] = mat[i][j];
                arr[(i-1)*n+j].r = i;
                arr[(i-1)*n+j].c = j;
                arr[(i-1)*n+j].v = mat[i][j];

            }
        }
        sort(arr+1,arr+n*n+1);
        int x,y;
        for (int i = 1 ; i <= n*n ; i ++)
        {
            x = arr[i].r , y = arr[i].c;
            for (int p = -k ; p <= k ; p ++)
            {
                if (check(x+p,y)&&mat[x+p][y]>mat[x][y])
                    dp[x][y] = max(dp[x][y],dp[x+p][y]+mat[x][y]);
                if (check(x,y+p)&&mat[x][y+p]>mat[x][y])
                    dp[x][y] = max(dp[x][y],dp[x][y+p]+mat[x][y]);
            }
        }
        printf("%d\n",dp[1][1]);


    }

    return 0;
}

Posted on Edited on In ,

题目链接：
https://vjudge.net/contest/170340#problem/C

题目大意：
有三个骰子，分别为k1,k2,k3k1,k2,k3面，同时，存在a,b,ca,b,c，当三个骰子的点数恰好依次是a,b,ca,b,c时，得分归零，否则得到三个骰子点数总和的分，求得分大于n的期望轮数是多少

分析：
概率正推，期望逆推，如果没有归零的条件，显然可以用dp[i]表示当前得分为i，到达目标的期望，写出dp转移式

dp[i]=∑k=3k<=k1+k2+k3dp[i+k]∗pk+1dp[i]=\sum_{k=3}^{k<=k1+k2+k3}dp[i+k]*p_k+1

pkp_k表示得到k分的概率，那么加上归零这个条件，写出的转移式则应该是

dp[i]=∑k=3k≤k1+k2+k3dp[i+k]∗pk+dp[0]∗p0+1dp[i]=\sum_{k=3}^{k\leq k1+k2+k3}dp[i+k]*p_k+dp[0]*p_0+1

而dp[0]就是我们所需要求的答案，是一个常数，在dp的过程中每一项都出现，所以可以将dp[0]设为未知量，则dp[i]都仅与dp[0]有关，设dp[i]

dp[i]=A[i]∗dp[0]+B[i]dp[i] = A[i]*dp[0] + B[i]

最后将该式代入原转移式，得到

dp[i]=∑k=3k≤k1+k2+k3(A[i+k]∗dp[0]+B[i+k])∗pk+dp[0]∗p0+1dp[i] = \sum_{k=3}^{k\leq k1+k2+k3}(A[i+k]*dp[0]+B[i+k])*p_k+dp[0]*p_0+1

联立两式，显然又

A[i]=∑k=3k≤k1+k2+k3A[i+k]∗pk+p0A[i] = \sum_{k=3}^{k\leq k1+k2+k3}A[i+k]*p_k+p_0

B[i]=∑k=3k≤k1+k2+k3B[i+k]∗pk+1B[i] = \sum_{k=3}^{k\leq k1+k2+k3}B[i+k]*p_k+1

最后根据

dp[0]=A[0]∗dp[0]+B[0]dp[0] = A[0]*dp[0] + B[0]

即可解得答案

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#define inf 0x3fffffff
using namespace std;




double dp[200];
double A[600],B[600];
int n,k1,k2,k3,a,b,c;

int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        memset(dp,0,sizeof(dp));
        memset(A,0,sizeof(A));
        memset(B,0,sizeof(B));
        scanf("%d%d%d%d%d%d%d",&n,&k1,&k2,&k3,&a,&b,&c);
        dp[0] = 1.0/k1/k2/k3;
        for (int i = 1 ; i <= k1 ; i ++)
        {
            for (int j = 1 ; j <= k2 ; j ++)
            {
                for (int k = 1 ; k <= k3 ; k++)
                {
                    if (i==a&&j==b&&k==c)
                        continue;
                    dp[i+j+k] += dp[0];
                }
            }
        }
        for (int i = n  ; i >= 0 ; i --)
        {
            for (int j = 3 ; j <= k1+k2+k3 ; j ++)
            {
                A[i]+= A[i+j]*dp[j]; 
                B[i]+= B[i+j]*dp[j];
            }
            A[i]+=dp[0];
            B[i]+=1;
        }
        printf("%.12f\n",B[0]/(1-A[0]));
    }
}

Posted on Edited on In ,

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=5738
题目大意：
给定n个点，(n<=1000)(n<=1000)，其中共线的点可加入同一个集合，集合中至少有两个元素，重点与任何点（包括本身）可视作共线，求有多少个这样的集合？
分析：
首先要得到所有共线的点，同时判重也是个问题，显而易见需要对点排序，一般是按x坐标从小到大，x坐标相同y坐标从小到大，然后遍历每一个点对

1
2
3
4
5
6
for (int i = 1 ; i <= n ; i ++)
{
    for (int j = i + 1 ; j <= n ; j ++)
    {
    }
}

对每个点对得到一个斜率，斜率使用分数形式存在结构体中，创建分数到出现次数的映射，map<fen,int>map<fen , int >分数需要最简形式，同时特判，如果分子分母同时为0，当前点重点的计数+1，最后得到与当前点重合的点的个数，然后计算当前点的总集合数，首先当前点（Point iPoint{\space}i）必取，然后任意一点与他均共线，从与它不重合的所有点中取，若有n个点与当前点共一线，则取法数为Cn1+Cn2+Cn3+⋯+Cnn=2n−1C_n^1+C_n^2+C_n^3+{\cdots}+C_n^n = 2^n-1,但是还要考虑重点，假设有m个重点，在所有集合中，重点均可取0,1,2,3⋯,m0,1,2,3{\cdots},m个，即取法种数为C0m+C1m+C2m+C3m+⋯+Cm−1m+Cmm=2mC_0^m+C_1^m+C_2^m+C_3^m+{\cdots}+C_{m-1}^m+C_m^m = 2^m，总的集合数即为2m∗(2n−1)2^m*(2^n-1)种，遍历集合同时取模即可，最后记得加上只选重点时的集合数，即为2m−12^m-1种，数据应该会爆intint，复杂度O(n2lgn)O(n^2lgn)。

代码（代码略长，多校时临场写的）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<map>
#include<deque>
#include<cmath>
#include<algorithm>

using namespace std;
long long MODA = 1e9 + 7;
const int MAXN = 200050;

inline void print(char pt) {
    printf("%c\n", pt);
}
inline void print(int pt) {
    printf("%d\n", pt);
}
inline void print(long long pt) {
    printf("%I64d\n", pt);
}
inline void print(double pt) {
    printf("%.20f\n", pt);
}
inline void print(char pt[]) {
    printf("%s\n", pt);
}
inline void print() {
    printf("\n");
}
inline void scan(int &pt) {
    scanf("%d", &pt);
}
inline void scan(char &pt) {
    scanf("%c", &pt);
}
inline void scan(long long &pt) {
    scanf("%I64d", &pt);
}
inline void scan(double &pt) {
    scanf("%lf", &pt);
}
inline void scan(char pt[]) {
    scanf("%s", pt);
}
struct pii {
    long long a;
    long long b;
    friend int operator<(pii a, pii b) {
        if (a.a != b.a)
            return a.a < b.a;
        return a.b < b.b;
    }
};

struct str {
    char val[1005];
    str() {
        memset(val, 0, sizeof(val));
    }
    friend int operator<(str a, str b) {
        return strcmp(a.val, b.val) < 0;
    }
};

long long gcd(long long x, long long y) {
    return y ? gcd(y, x % y) : x;
}
long long lcm(long long x, long long y) {
    return x * (y / gcd(x, y));
}

int bits[50];
void getbits() {
    for (int i = 0; i < 30; i++) {
        bits[i] = 1 << i;
    }
}

long long Q_pow(long long x, long long y) {
    long long res = 1;
    while (y) {
        if (y % 2 == 1) {
            res *= x;
            res %= MODA;
        }
        x = x * x;
        x %= MODA;
//        if(x<=1e-5){
//            return 0;
//        }
        y /= 2;
    }
    return res;
}

//返回d=gcd(a,b);和对应于等式ax+by=d中的x,y
long long extend_gcd(long long a, long long b, long long &x, long long &y) {
    if (a == 0 && b == 0)
        return -1; //无最大公约数
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long d = extend_gcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
//*********求逆元素*******************
//ax = 1(mod n)
long long mod_reverse(long long a, long long MOD) {
    long long x, y;
    long long d = extend_gcd(a, MOD, x, y);
    if (d == 1)
        return (x % MOD + MOD) % MOD;
    else
        return -1;
}


struct point {
    long long x, y;
    friend int operator<(const point &a, const point &b) {
        if (a.x != b.x)
            return a.x < b.x;
        return a.y < b.y;
    }

    friend int operator==(const point &a, const point &b) {
        return (a.x == b.x) && (a.y == b.y);
    }
};

struct fenshu {
    long long fenzi, fenmu;
    void zhengqi() {
        if (fenzi == 0 && fenmu == 0) {

        } else if (fenzi == 0) {
            fenmu = 1;
        } else if (fenmu == 0) {
            fenzi = 1;
        } else {
            if (fenmu < 0) {
                fenzi = -fenzi;
                fenmu = -fenmu;
            }
            int flag0 = (fenzi < 0);
            if (flag0) {
                fenzi = -fenzi;
            }
            int nowgcd = gcd(fenzi, fenmu);
            fenzi /= nowgcd;
            fenmu /= nowgcd;
            if (flag0) {
                fenzi = -fenzi;
            }
        }
    }
    friend int operator<(const fenshu &a, const fenshu &b) {
        if (a.fenzi != b.fenzi)
            return a.fenzi < b.fenzi;
        return a.fenmu < b.fenmu;
    }

};

int h, n, m, w;
point a[100050];
int endof[100050];
long long pow2[1050];

map<fenshu, int> mapfenshu;
int main() {
    long long ti = 1;
    for (int i = 0; i < 1050; i++) {
        pow2[i] = ti;
        ti *= 2;
        ti %= MODA;
    }

    int T;
    scan(T);
    while (T--) {
        scan(n);
        for (int i = 0; i < n; i++) {
            scan(a[i].x);
            scan(a[i].y);
        }
        sort(a, a + n);
        endof[n - 1] = n - 1;
        for (int i = n - 2; i >= 0; i--) {
            if (a[i + 1] == a[i]) {
                endof[i] = endof[i + 1];
            } else {
                endof[i] = i;
            }
        }

        long long ansa = 0;
        for (int i = 0; i < n; i++) {
            int chongdian = endof[i] - i;
            mapfenshu.clear();
            for (int j = endof[i] + 1; j < n; j++) {

                fenshu newf;
                newf.fenmu = a[j].x - a[i].x;
                newf.fenzi = a[j].y - a[i].y;
                newf.zhengqi();
                mapfenshu[newf]++;
            }

            for (auto au : mapfenshu) {
                ansa += (pow2[chongdian]) * (pow2[au.second] - 1);
                if (ansa < 0)
                    ansa += MODA;
                ansa %= MODA;
            }
            ansa += pow2[chongdian] - 1;
            if (ansa < 0)
                ansa += MODA;
            ansa %= MODA;
        }
        print(ansa);
    }
    return 0;
}

Posted on Edited on In ,

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=1671

题目大意：
给出nn个字符串，询问是否存在某个串完全为另一个串的前缀

分析：
将字符串按长度排序后插入即可，当前字符串插入字典树时，若中途发现该结点为单词，说明该单词的前缀已被插入，返回falsefalse，若全部能顺利插入则返回truetrue

注意：如果使用指针构造字典树，交G可能会爆空间，建议交C

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;

typedef long long ll;


struct Trie{
    Trie *next[10];
    int val;
    Trie(){
        val = 0;
        for (int i = 0 ; i < 10 ; i ++)
            next[i] = NULL;
    }
};

bool addword(char *str,Trie* node)
{

    if (node->val!=0)
        return false;
    if (node->next[str[0]-'0']==NULL)
        node->next[str[0]-'0'] = new Trie;
    node = node->next[str[0]-'0'];
    str++;
    //printf("%d\t",*str);
    if (*str)
        return addword(str,node);
    else
    {
        node->val++;
        return true;
    }
}

int query(char *str ,Trie *node)
{
   // printf("%d\t",*str);
    if (node->next[*str-'0']==NULL)
        return 0;
    else
        node= node->next[*str-'0'];
    ++str;
    if (*str)
        return query(str,node);
    else
        return node->val;
}

void del(Trie *node)
{
    for (int i = 0 ; i < 10 ; i ++)
    {
        if (node->next[i]!=NULL)
            del(node->next[i]);
    }
    delete node;
    node = NULL;
    return;
}
struct String{
    char str[20];
    int len;
    void read()
    {
        scanf("%s",str);
        len = strlen(str);
    }
    bool operator <(const String& a)
    {
        return len<a.len;
    }
}s[12000];


int main()
{
    int T,n;
    //printf("hello\n");
    Trie *head;
    //printf("world\n");
    scanf("%d",&T);

    while (T--)
    {

        scanf("%d",&n);
        head = new Trie;
        for (int i = 1;  i <= n ; i ++)
        {
            s[i].read();
        }
        sort(s+1,s+n+1);
        int f = 1;
        //printf("ok\n");
        for (int i = 1 ; i <= n ; i ++)
        {
            if (!addword(s[i].str,head))
            {
                f = 0;
                break;
            }
        }
        //printf("fuck\n");
        if (!f)
            printf("NO\n");
        else
            printf("YES\n");
        del(head);

    }

    return 0;
}

Posted on Edited on In ,

问题：
把一个读入的十进制数字以十六进制的形式输出，同时统计转换成的十六进制数字的长度。

分析：
非常经典的一类问题，只要递归一下，或者用堆栈，或者16进制可以选择二进制顺序每四位读取等等多种方式

代码：
只是试试写在一行里，行数是少了，可读性比较差

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>


int Print_Decimal(int n)
{
    return (n&(1<<31)?putchar('-'),n*=(~0):0),(!(n>>4)?(n += 1<<4):(n = ((Print_Decimal(n>>4)+1<<4)+(n&15)))),putchar((n&15)+'0'+(((n&15)>9)?7:0)),n>>4;
}


int main()
{
    int number;
    scanf("%d",&number);
    int len = Print_Decimal(number);
    printf("\nlen = %d\n",len);
    return 0;
}

Posted on Edited on In ,

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=3555

题目大意：
给定一个NN，找出1−N1-N间含有子串49的数字个数

分析：
这个和不要62类似，但是略有不同，现在找的是含有49的数，所以一样记一个参数pre，代表前一个数位的值，然后记一个sta，这个和不要62中的sta有些不同，有三重状态

  • sta = 0前一个数位不是6
  • sta = 1前一个数位是6
  • sta = 2之前出现过49
    显然最后pos==−1pos==-1的时候，只有sta==2sta==2的结果才能返回1

另外对于当sta=2时，当前位无论如何放置都不会改变sta的值，而对于其他情况，类似不要62

分析：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;

ll dp[30][10];

int a[50],pos;

ll dfs(int pos,int pre,int sta,bool limit)
{
    if (pos==-1)
    {
        return sta==2;
    }

    if (!limit&&dp[pos][sta]!=-1)  {
        //printf("dp[%d][%d] = %lld\n",pos,sta,dp[pos][sta]);
        return dp[pos][sta];
    }
    int up = limit?a[pos]:9;
    ll ans = 0;
    for (int i = 0 ; i <= up ; i ++)
    {
        int temp = sta;
        if (pre==4&&i==9)
            temp = max(temp,2);
        else if (i==4)
            temp = max(temp,1);
        else
        {
            if (temp!=2)
                temp = 0;
        }
        ans += dfs(pos-1,i,temp,limit&&i==pos[a]);
    }
    if (!limit) dp[pos][sta] = ans;
    return ans;
}


ll solve(ll n)
{
    pos = 0;
    while (n)
    {
        a[pos++] = n%10;
        n /= 10;
    }
    return dfs(pos-1,0,0,true);
}

int main()
{
    ll n;
    int T;
    scanf("%d",&T);
    memset(dp,-1,sizeof(dp));
    while (T--)
    {
        scanf("%lld",&n);
        printf("%lld\n",solve(n));
    }
}

Posted on Edited on In ,

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=1025

题目大意：
每个偏僻城市可以接受繁荣城市的援助，但是相互之间的援助不能交差，这里写图片描述
如图所示的援助是非法的

分析：
显然是直接做一个LIS，最长上升子序列，但是这题的数据量有些大，直接n2n^2dp是过不去的，所以需要优化成nlognnlogn，看刘汝佳的代码比较清楚,g[i]表示长度为i的子序列的最小结尾，dp[i]表示以i为结尾，递增子序列的最大长度，最后要注意这题容易输出错误，只有一条路时输出1 road，超过1条路则输入k roads，算一个坑点

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;

const int maxn = 520000;
const int INF = 0x3f3f3f3f;
int n,p,r;
int arr[maxn],g[maxn],dp[maxn];

int main()
{
    int t = 1 ;
    while (~scanf("%d",&n))
    {
//        if (t!=1)
//            putchar('\n');
        for (int i = 1 ; i <= n ; i ++)
        {
            scanf("%d%d",&p,&r);
            arr[p] = r;
        }
        memset(g,0x3f,sizeof(g));
        memset(dp,0,sizeof(dp));

        for (int i = 1 ; i <= n ; i ++)
        {
            int pos = lower_bound(g+1,g+n+1,arr[i])-g;
            dp[i] = pos;
            g[pos] = arr[i];
        }

        int maxx  =0 ;
        for (int i = 1 ; i <= n ; i ++)
            maxx = max(maxx,dp[i]);
        printf("Case %d:\n",t++);
        if (maxx==1)
            printf("My king, at most %d road can be built.\n\n",maxx);
        else
            printf("My king, at most %d roads can be built.\n\n",maxx);
    }

    return 0;
}

Posted on Edited on In ,

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=1247

题目大意：
给出一个单词表，询问其中是否存在某些单词，如hat-word，是由表中其他两个单词拼接得到的，输出所有的这样的单词

分析：
直接将单词全部插入字典树，然后暴力枚举每个单词的所有分割可能即可

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#include<map>
#include <string>
using namespace std;

typedef long long ll;


struct Trie{
    Trie *next[26];
    int val;
    Trie(){
        val = -1;
        for (int i = 0 ; i < 26 ; i ++)
            next[i] = NULL;
    }
};

void addword(string& str,Trie* node,int i)
{
    if (node->next[str[i]-'a']==NULL)
        node->next[str[i]-'a'] = new Trie;

    node = node->next[str[i]-'a'];
    ++i;
    if (i<str.size())
        addword(str,node,i);
    else
    {
        node->val = 1;
        return;
    }
}


int query(string & str ,Trie *node,int i)
{
    if (node->next[str[i]-'a']==NULL)
        return -1;
    else
        node= node->next[str[i]-'a'];
    ++i;
    if (i<str.size())
        return query(str,node,i);
    else
        return node->val;
}

string str[100000];


int main()
{
    int cnt=0;
    string p,q;
    Trie* head = new Trie;
    ios::sync_with_stdio(false);
    while (cin>>str[cnt])
    {
        addword(str[cnt],head,0);
        cnt++;
    }
    sort(str,str+cnt);
    for (int i = 0 ; i < cnt ; i ++)
    {
        p.clear();
        q.clear();
        for (int j = 0 ; j < str[i].size()-1 ;j ++)
        {
            p +=str[i][j];
            q = str[i].substr(j+1);
            //cout<<" p = "<<p<<"  q = "<<q<<endl;
            if (query(p,head,0)!=-1&&query(q,head,0)!=-1)
            {
                cout<<str[i]<<endl;
                break;
            }
        }
    }



    return 0;
}

Posted on Edited on In ,

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=6069

题目大意：
给定区间[l,r][l,r]和kk，$$d(i) = \sum_{d=1,d|n}{n}1$$求式子$$\sum_{i=l}{r}d(i^k)$$的值，结果对998244353取模

分析：
区间长度为1e6，数据有10组以上，暴力分解整个区间的话，每个数的分解至多是logn级别的，而基于Miller_Robin的质因数分解polard_rho也只是O(n14)O(n^{\frac{1}{4}})级别的，远远达不到要求，所以不能从对每个数分解质因数上想，而是试着用[2,r][2,\sqrt r]内的所有质因子去筛[l,r][l,r]区间内的数，最后在除尽了这些因子后的数，要么是1，要么是一个大的质因子，且次数至多为1，因为如果大于sqrtrsqrt r的因子次数大于1，这个数的大小就会大于rr，产生矛盾

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>

using namespace std;


typedef long long ll;


const ll mod = 998244353;
const int maxn = 1e6+100;

ll l,r,k;
int len;
bool isprime[maxn+200];
int prime[maxn];



ll divi[maxn];
ll cnt[maxn];

void init()
{
    for (int i =2 ; i <= maxn; i ++)
    {
        if (!isprime[i])
        {
            prime[++prime[0]] = i;
            for (int j = i +i ; j <= maxn ; j+= i)
                isprime[j] = true;
        }
    }
}

void solve()
{
    int st;
    for (int i = 1 ; prime[i]<= r/prime[i] && i<= prime[0] ; i ++)
    {
        //printf("i = %d\n",prime[i]);
        if (l%prime[i]==0)
            st = 1;
        else
            st = 1 + (prime[i]-l%prime[i]);
        for (int j = st ; j <= len ; j +=prime[i])
        {
            int ct = 0;
            while (divi[j]%prime[i]==0)
            {
                divi[j]/=prime[i];
                ct++;
            }
            cnt[j]*=(ct*k+1);
            if (cnt[j]>=mod)
                cnt[j] %= mod;
        }
    }
    ll ans = 0;
    for (int i =1 ; i <= len ; i ++)
    {
        if (divi[i]!=1)
            cnt[i] = cnt[i] * (k+1)%mod;
        //printf("divi[%d] = %lld\n",i,divi[i]);
        ans += cnt[i];
        if (ans>=mod)
            ans %= mod;
    }
    printf("%lld\n",ans);
}


int main()
{
    init();
    //printf("prime[0] = %d\n",prime[0]);
    int T;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%lld%lld%lld",&l,&r,&k);
        len = (int)(r- l +1);
        for (int i = 1 ; i <= len ; i ++)
        {
            divi[i] = l + i -1;
            cnt[i] = 1;
        }

        solve();



    }
    return 0;
}

Posted on Edited on In ,

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=6060

题目大意：
一颗以结点11为根的树，对2−n2-n的结点作一个划分，但至多使用k个集合，对每个分块产生的集合中加入根节点1，然后计算集合内结点互相可达最少需要的权值的和（非最小生成树，可能需要经过其他结点），求权值和的最大可能值

分析：
若要使权值和最大，考虑每一条边的贡献次数，如果从父亲向下的一条边，子树大小小于k，设为x，下面至多被分为x个分块，该边被贡献x次，否则至多分成k个分块，该边贡献k次，所以每条边最大情况下应该被计算min(x,k)min(x,k)次，x为该边下方结点的子树大小

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include<bits/stdc++.h>

using namespace std;

const int N = 1000006;
const int M = N * 2;
const long long INF = 1e11 + 10;

int n, k;
long long dis[N];
pair<long long, int> son[N];
long long ans;
int fa[N];
int use[N];
int sz[N];

struct Edge{
    int v, nxt;
    long long w;
}e[M];
int h[N];
int cnt;

struct Node{
    int u, w;
    
    Node(){}
    Node(int x, int y) : u(x), w(y){}
    bool operator <(const Node &x)const{
        return w > x.w;
    }
};

void init(){
    memset(h, -1, sizeof(h));
    cnt = 0;
}

void add(int x, int y, long long z){
    e[cnt].v = y;
    e[cnt].w = z;
    e[cnt].nxt = h[x];
    h[x] = cnt++;
}

void dij(){
    for(int i = 2; i <= n; i++) dis[i] = INF;
    dis[1] = 0;

    priority_queue<Node> Q;
    Q.push(Node(1, dis[1]));
    while(!Q.empty()){
        Node temp = Q.top(); Q.pop();
        int u = temp.u;
        if(temp.w > dis[u]) continue;
        for(int k = h[u]; ~k; k = e[k].nxt){
            int v = e[k].v;
            if(dis[v] > dis[u] + e[k].w){
                dis[v] = dis[u] + e[k].w;
                Q.push(Node(v, dis[v]));
            }
        }
    }
}

int q[N];
void bfs(){
    memset(fa, -1, sizeof(fa));
    fa[1] = 0;
    
    int be = 0, ed = 0;
    q[ed++] = 1;
    while(be < ed){
        int u = q[be++];
        for(int k = h[u]; ~k; k = e[k].nxt){
            int v = e[k].v;
            if(fa[v] != -1) continue;
            fa[v] = u;
            q[ed++] = v;
        }
    }

    for(int i = n - 1; i >= 0; i--){
        sz[q[i]]++;
        sz[fa[q[i]]] += sz[q[i]];
    }
}

int find(int x){
    if(fa[x] == 1) return fa[x] = x;
    else return x == fa[x] ? x : fa[x] = find(fa[x]);
}

void solve(int u){
    for(int kk = h[u]; ~kk; kk = e[kk].nxt){
        int v = e[kk].v;
        if(fa[v] != u) continue;
        if(sz[v] > k){
            ans -= (sz[v] - k) * (dis[v] - dis[fa[v]]);
            solve(v);
        }
    }
}

int main(){
    while(~scanf("%d%d", &n, &k)){
        init();
        ans = 0;
        memset(use, 0, sizeof(use));
        memset(sz, 0, sizeof(sz));

        int u, v;
        long long w;
        for(int i = 1; i < n; i++){
            scanf("%d%d%lld", &u, &v, &w);
            add(u, v, w);
            add(v, u, w);
        }

        dij();

        for(int i = 2; i <= n; i++)
            ans += dis[i];

        bfs();

        solve(1);

        printf("%lld\n", ans);
    }

    return 0;
}