CheaSim Blog
发表更新学习笔记5 分钟读完 (大约722个字)

[acm]hash学习笔记

hash学习

hash是一种比较常见的处理字符串的手法。在acm题目中，经常使用hash来处理字符串。比如判断一个子串在一个字符串中出现过几次。就可以使用hash来处理。

hash主要的方法就是把不同的字符串对应到不同的数字，之后通过数组来确定字符串是否出现过，从而减少检索字符串的时间。

常见的hash方法

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef unsigned long long ull;
ull base[maxn],has[maxn];
void init(){
    base[0] = 1;
    rep(i,1,maxn) base[i] = base[i-1] * 131;
	scanf("%s",s);
    int len = strlen(s);
    has[len] = 0;
    per(i,0,len) has[i] = has[i+1]*131 + (s[i]-'a'+1);
}
ull get_hash(int i,int L){
    return has[i] - has[i+L]*base[L];
}

练习

hdoj4821 String

题目大意就是求$S$子串中，

  • 长为$M*L$
  • 其中每一段连续的$L$长度的子串都各不相同。

就是使用hash来做。但是我TLE了。因为暴力了每一段的hash值。

其实由于如果$S$的长度很长的话。其中很多段子段的hash值是被反复求的。所以我们在求完一段$M$个的字符串之后，就可以按照这个把第一段去除。之后选择后一段。这样重复下去。

Wa1:等于号想清楚了在判定。

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
typedef unsigned long long ull;
const int maxn = 1e5+10;
ull xp[maxn],Hash[maxn];
void init(){
    xp[0] = 1;
    rep(i,1,maxn) xp[i] = xp[i-1] * 175;
}
ull get_Hash(int i,int L){
    return Hash[i] - Hash[i+L] * xp[L];
}
int n,m;
char s[maxn];
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    init();
    // m = length of L
    while(~scanf("%d%d",&n,&m)){
        scanf("%s",s);
        int len = strlen(s);
        Hash[len] = 0;
        per(i,0,len){
            Hash[i] = Hash[i+1]*175+(s[i]-'a'+1);
        }
        int ans = 0;
        for(int i=0;i<m && i<=len-m*n;i++){
            map<ull,int> mx;
            for(int j=i;j<i+m*n;j+=m){
                ull temp = get_Hash(j,m);
                mx[temp] ++;
            }
            if(mx.size() == n) ans++;
            for(int j = i+n*m;j+m<=len;j+=m){
                ull temp = get_Hash(j-n*m,m);
                mx[temp]--;
                if(mx[temp] == 0) mx.erase(temp);
                temp = get_Hash(j,m);
                mx[temp]++;
                if(mx.size() == n) ans++;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

hdoj4080 Stammering Aliens

题目大意是找到字符串$S$中，出现次数大于$m$次并且最长的字符串。

我是用hash做的，不过时间是4800ms，差点超时。用别人后缀数组＋二分，200ms可以过。。

就酱吧。

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<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
//head

const int maxn = 4e4+10;
ull base[maxn],has[maxn];
void init(){
    base[0] = 1;
    rep(i,1,maxn) base[i] = base[i-1] * 131;
}
ull get_hash(int i,int L){
    return has[i] - has[i+L] * base[L];
}

int m,n;
char s[maxn];
int check(int len){
    map<ull,int> mx;
    int ans = -1;
    rep(i,0,n-len+1) {
        ull temp = get_hash(i,len);
        mx[temp] ++;
        if(mx[temp] >= m){
            ans = i;
        }
    }
    return ans;
}
int right_most = 0;
int res = 0;
void solve(int l,int r){
    int mid;
    while(l<=r){
        mid = l+r>>1;
        int temp = check(mid);
        if(temp != -1){
            l = mid + 1;
            res = mid;
            right_most = temp;
        }else{
            r = mid - 1;
        }
    }
}
int main(){
#ifdef LOCAL
    freopen("2.in","r",stdin);
#endif
    init();
    while(scanf("%d",&m) && m){
        scanf("%s",s);
        n = strlen(s);
        has[n] = 0;
        per(i,0,n) has[i] = has[i+1] * 131 + s[i] - 'a' + 1;
        right_most = 0; res = 0;
        solve(1,n+1);
        if(res == 0){
            puts("none");
        }else{
            printf("%d %d\n",res,right_most);
        }
    }

    return 0;
}

reference:

https://blog.csdn.net/u012965373/article/details/38929637

https://blog.csdn.net/ck_boss/article/details/47066727

发表更新dfs2 分钟读完 (大约285个字)

[hdoj2260]Difficulty control(dfs)

Difficulty Control

题意

中文题目不说了。

题解

dfs+剪枝

  • 剩下的加不到最优值剪掉
  • 已经加过了最优值剪掉

我在大二的时候TLE了20次的题目终于在队友的指导之下完成了。

ac代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head

ll n,m;
const int maxn = 30;
ll num[maxn];
vector<int> ve;
ll ans = INT_MAX;
int tans[maxn];
int temp[maxn];
void dfs(int x,ll now){
    if(abs(now-m) < ans && x == n){
        ans = abs(now-m);
        memcpy(tans,temp,sizeof(temp));
    }
    ll tt = 0;
    if(now-m > ans) return;
    rep(i,x,n) tt += num[ve[i]];
    if(tt + now + ans < m ) return ;
    if(x==n) {
        return ;
    }
    temp[ve[x]] = 1;
    dfs(x+1,now + num[ve[x]]);
    temp[ve[x]] = 0;
    dfs(x+1,now);
}
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    while(cin>>n>>m){
        ve.clear();
        memset(temp,0,sizeof(temp));
        memset(tans,0,sizeof(tans));
        rep(i,0,n){
            ll x; char ch; cin>>ch>>x;
            ve.push_back(ch-'A');
            num[ch-'A'] = x;
        }
        sort(ve.begin(),ve.end());
        ans = INT_MAX;
        dfs(0,0);
        vector<int> reans;
        rep(i,0,26) if(tans[i]) reans.push_back(i+'A');
        int len = reans.size();
        printf("%d\n",len);
        rep(i,0,len){
            printf("%c%c",reans[i],i==len-1?'\n':' ');
        }
    }
    return 0;
}
发表更新cf3 分钟读完 (大约425个字)

[cf541D]Gourmet choice (缩点+dfs)

Gourmet choice

题意

给定$n$个蛋糕和$m$个蛋糕，和他们之间的大小关系。问给所有的蛋糕一个可能最小的值，使得关系成立。

题解

首先由于有$=$的存在，有一些蛋糕的值是要一样的。所以我们需要把题目中的相等的点给缩到一起。

之后用dfs把值给确定下来。

其中缩点用到的技巧很厉害。

ac代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 2e3+10;
vector<int> e[maxn];
// m is behind of the n
int fa[maxn];
int Find(int x){
    return fa[x] == x ? x : fa[x] = Find(fa[x]);
}
void Union(int i,int j){
    int x = Find(i);
    int y = Find(j);
    if(x!=y) fa[x] = y;
}
int ind[maxn],use[maxn],vis[maxn];
char mx[maxn][maxn];
int n,m;
// flag means the 矛盾
bool flag;
int dp[maxn];
void dfs(int x,int dep){
    if(flag) return ;
    dp[x] = max(dp[x],dep);
    for(auto to:e[x]){
        if(vis[to]) {
            flag = true;
            return ;
        }
        if(dep+1>dp[to]){
            vis[to] = 1;
            dfs(to,dep+1);
            vis[to] = 0;
        }
    }
}
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    rep(i,0,n){
        scanf("%s",mx+i);
    }
    rep(i,0,n+m) fa[i] = i;
    rep(i,0,n)
        rep(j,0,m)
            if(mx[i][j] == '=')
                Union(i,n+j);
    rep(i,0,n) rep(j,0,m){
        int x = Find(i); int y = Find(j+n);
        if(mx[i][j] == '<'){
            e[x].push_back(y);
            ind[y] ++;
            use[x] = 1;
        }else if(mx[i][j] == '>'){
            e[y].push_back(x);
            ind[x] ++;
            use[y] = 1;
        }else{
            use[x] = 1;
        }
    }
    bool fflag = false;
    rep(i,0,n+m){
        if(use[i] && ind[i] == 0){
            fflag = true;
            vis[i] = 1;
            dfs(i,1);
            vis[i] = 0;
        }
    }
    if(fflag == false || flag){
        puts("No");
    }else{
        puts("Yes");
        rep(i,0,n) printf("%d ",dp[Find(i)]);
        puts("");
        rep(i,n,m+n) printf("%d ",dp[Find(i)]);
    }
    return 0;
}
发表更新dp2 分钟读完 (大约364个字)

[cf706C]Hard Problem

706C - Hard problem

题意

题意很简单，就是给定$n$串字符串，对每一串字符串只有一种操作，翻转。之后每翻转一个字符串需要消耗$c_i$的能量，问至少需要多少能量是的，这$n$个字符串是以字典序排列的。

ps:相等也算按字典序

题解

dp，定义一个二维数组$dp[i][j]$。其中$i$表示第$i$个字符串中选择$j$产生字典序的最少能量消耗。$j$只有1和0，表示翻转或者不翻转，之后就是四种情况下去。具体可以看代码.

ac代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head

ll n,m,q;
ll d;
const int maxn = 210;
ll num[maxn];
ll dp[maxn][12][22];
ll a[maxn];
ll MOD(ll x,ll mod){
    ll tx = x % mod;
    if(tx<0) tx += mod;
    return tx;
}
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    int T; scanf("%d",&T);
    rep(test_case,1,T+1){
        scanf("%lld%lld",&n,&q);
        rep(i,1,n+1) scanf("%lld",num+i);
        printf("Case %d:\n",test_case);
        while(q--){
            scanf("%lld%lld",&d,&m);
            rep(i,1,n+1) a[i] = MOD(num[i],d);
            memset(dp,0,sizeof(dp));
            rep(i,0,n) dp[i][0][0] = 1;
            rep(i,1,n+1){
                rep(j,1,m+1){
                    rep(k,0,d) dp[i][j][k] = dp[i-1][j][k];
                    rep(k,0,d){
                        dp[i][j][(k+a[i])%d] += dp[i-1][j-1][k];
                    }
                }
            }
            printf("%lld\n",dp[n][m][0]);
        }
    }
    return 0;
}
发表更新cf9 分钟读完 (大约1406个字)

Codeforces Round #542

Codeforces Round #542

A. Be Positive

题意

给定一个数组$a_1,a_2,…,a_n$，让你到一个数字，是的数组内的所有数字处以这个数字之后，数组内大于0的数字超过$\cfrac{n}{2}$的上界。

题解

由于没有要求整除，所以直接看负数多还是正数多，哪个超过上届，就用$-1或者1$

ac代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int n;
const int maxn = 1e3+10;
int a[maxn];
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    scanf("%d",&n);
    int cnt1=0,cnt2=0;
    rep(i,0,n){
        scanf("%d",a+i);
        if(a[i]>0) cnt1++;
        if(a[i]<0) cnt2++;
    }
    int ans = 0;
    if(n%2) n++;
    if(cnt1>=n/2) ans = 1;
    if(cnt2>=n/2) ans = -1;
    printf("%d",ans);
    return 0;
}

B. Two Cakes

题意

两个人要买$n$层蛋糕，他们必须从$1$开始买到$n$，之后给定$2n$个蛋糕店，他们从$1$这个点出发，之后去买蛋糕。其中一旦一个人从一家蛋糕店买了蛋糕，那么另外一个人就不能在那家蛋糕店买蛋糕。问两个人花费的最少步数是多少？

题解

由于每一步只有两种可能，一个人去$x+1$中的一家蛋糕店，另外一个人去另一家。每一步的选择都只有两种，且无后效性。所以我们用贪心来解决。每一步的时候都选择花费步数最少的选择。

ac代码

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<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 1e5+10;
int n;
struct node{
    int idx,val;
    bool operator<(const node &x){
        return val < x.val;
    }
}a[maxn<<1];
int vis[maxn*2];
int main(){
#ifdef LOCAL
    freopen("2.in","r",stdin);
#endif
    scanf("%d",&n);
    rep(i,0,2*n){
        int x; scanf("%d",&x);        
        a[i].idx = i+1; a[i].val = x;
    }
    sort(a,a+2*n);
    int cnt = 0;
    int now1 = 1, now2 = 1;
    ll ans = 0;
    for(int i=0;i<2*n;i+=2){
        int temp = INF;
        int x1 = abs(now1 - a[i].idx) + abs(now2 - a[i+1].idx);
        int x2 = abs(now2 - a[i].idx) + abs(now1 - a[i+1].idx);
        if(x1>x2){
            now2 = a[i].idx;
            now1 = a[i+1].idx;
        }else{
            now1 = a[i].idx;
            now2 = a[i+1].idx;
        }
        ans += 1ll * min(x1,x2);
    }
    printf("%lld\n",ans);


    return 0;
}

C. Connect

题意

Alice要从一个陆地到另外一块陆地，需要建造一座大桥，问桥的花费要最少。

  • 桥的花费是欧几里得距离的平方
  • 只能建造一座桥
  • 可能不需要建造桥

题解

由于只建造一座桥，所以我们可以枚举起始点的陆地和终点的陆地，之后挑选出最近的点。

由于数据小，随便做。

ac代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int n;
int stx,sty,edx,edy;
int dir[4][2] = {1,0, -1,0, 0,1, 0,-1};
const int maxn = 100;
int vis[maxn][maxn];
char mx[maxn][maxn];
vector<pII > st;
vector<pII > ed;
void bfs(int x,int y,bool sign){
    vis[x][y] = 1;
    queue<pair<int,int> >q;
    q.push(make_pair(x,y));
    while(!q.empty()){
        int xx = q.front().first; int yy = q.front().second;
        q.pop();
        if(sign) st.push_back(make_pair(xx,yy));
        else ed.push_back(make_pair(xx,yy));
        rep(i,0,4){
            int xxx = xx + dir[i][0];
            int yyy = yy + dir[i][1];
            if(xxx<0 || xxx >=n || yyy<0 || yyy>=n) continue;
            if(mx[xxx][yyy] == '1') continue;
            if(vis[xxx][yyy])  continue;
            vis[xxx][yyy] = 1;
            q.push(make_pair(xxx,yyy));
        }
    }
}
int main(){
#ifdef LOCAL
    freopen("3.in","r",stdin);
#endif
    scanf("%d",&n);
    scanf("%d%d%d%d",&stx,&sty,&edx,&edy);
    stx--;sty--;edx--;edy--;
    rep(i,0,n){
        scanf("%s",mx+i);
    }
    int ans = INF;
    bfs(stx,sty,1);
    bfs(edx,edy,0);
    int len1 = st.size();
    int len2 = ed.size();
    rep(i,0,len1){
        rep(j,0,len2){
            int x1 = st[i].first;
            int y1 = st[i].second;
            int x2 = ed[j].first;
            int y2 = ed[j].second;
            ans = min(ans,(x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
        }
    }
    printf("%d\n",ans);
    return 0;
}

D2. Toy Train

题意

Alice开火车，他火车的轨道是确定的，之后火车开的方向也是确定的，火车的轨迹是一个圈，轨迹上有很多站点，每个站点上有糖果。

  • 火车在站点上只可以拿起一个糖果
  • 火车在站点上可以放下无限个糖果

目标是将所有站点上的糖果放到指定的站点所花费的时间最小。

题解

由于每一个站点都是独立的。你只需要管他是怎么拿起来的。所以每一个站点如果有$x$个糖果，那么从他开始至少要$x-1$圈加上一个最短的距离。所以我们可以枚举每一个站点所需要的最远距离。

假设从$i$起始点到$j$站点。那么我们开始的距离是$dis(i,j)=(j-i+n)\mod n$。

之后我们需要$x-1$圈。$(x-1)\times n$

之后我们需要从那个点到最近的放置点.$dis(j,z) = (z-j+n)\mod n$

之后两层循环即可。

ac代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 5e3+10;
const int maxm = 2e2+10;
int n,m;
vector<int> candys[maxn];
int ans[maxn];
int main(){
#ifdef LOCAL
    freopen("4.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    rep(i,0,m){
        int x,y;scanf("%d%d",&x,&y);
        candys[x-1].push_back(y-1);
    }
    int mmax = 0;
    rep(i,0,n){
        mmax = max(mmax,(int)candys[i].size());
    }
    // ans 
    rep(i,0,n){
        int ans = 0;
        rep(j,0,n){
            if(candys[j].size()==0)continue;
            int temp = (j-i+n)%n;
            int tx = INF;
            for(auto &x: candys[j]){
                tx = min(tx,(x-j+n)%n);
            }
            ans = max(ans, ((int)candys[j].size()-1)*n + tx + temp);
        }
        printf("%d ",ans);
    }
    return 0;
}
发表更新14 分钟读完 (大约2101个字)

jsp第七次作业

jsp大作业

作业要求

  • mysql + CRUD
  • 校验器
  • Struts2+Hibernate 框架
  • css美化

文件结构

![image-20181128192100403](/Users/cheasim/Library/Application Support/typora-user-images/image-20181128192100403.png)

运行截图

登陆界面

![image-20181128192157690](/Users/cheasim/Library/Application Support/typora-user-images/image-20181128192157690.png)

选择操作界面

![image-20181128192234733](/Users/cheasim/Library/Application Support/typora-user-images/image-20181128192234733.png)

增加和修改界面

使用了js语言，实现了一个form中有两个按钮，指向不同的action

![image-20181128192321558](/Users/cheasim/Library/Application Support/typora-user-images/image-20181128192321558.png)

校验器

应用对加入学生信息进行校验。

ID必须为0或者不为0开头的数字。

name和address不能为空。

![image-20181128192708351](/Users/cheasim/Library/Application Support/typora-user-images/image-20181128192708351.png)

成功添加后自动转到学生列表(改变也是一样)

![image-20181128192747889](/Users/cheasim/Library/Application Support/typora-user-images/image-20181128192747889.png)

查询和删除

因为用户可能不确定要删除哪一个，所以删除的旁边还有一个查询按钮。根据ID来进行查询。

![image-20181128192905933](/Users/cheasim/Library/Application Support/typora-user-images/image-20181128192905933.png)

![image-20181128192914679](/Users/cheasim/Library/Application Support/typora-user-images/image-20181128192914679.png)

代码

接口代码

![image-20181128193135141](/Users/cheasim/Library/Application Support/typora-user-images/image-20181128193135141.png)

1
2
3
4
5
6
7
8
9
10
11
package njtech.edu.DAO;

import java.util.List;

import org.hibernate.Session;

public interface BaseDAO {
    public Session getSession();
    public void closeSession();
    public List search(String hql);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
package njtech.edu.DAO;


import java.util.List;
import njtech.edu.model.Student;

public interface StudentDAO {
    void saveStudent(Student student);

    List<Student> getAll();
    void changeStudent(Student student);
    void deleteStudent(Student student);
    List<Student> queryStudent(Student student);
}
1
2
3
4
5
6
7
8
9
10
11
package njtech.edu.DAO;

import njtech.edu.model.User;

import java.util.List;

public interface UserDAO {

    User queryUser(String username);
}

实现类代码

![image-20181128193145593](/Users/cheasim/Library/Application Support/typora-user-images/image-20181128193145593.png)

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
package njtech.edu.DAO.impl;

import java.util.List;

import com.googlecode.s2hibernate.struts2.plugin.util.HibernateSessionFactory;
import njtech.edu.DAO.BaseDAO;
import njtech.edu.DAO.StudentDAO;
import org.hibernate.Query;
import org.hibernate.Session;
import org.hibernate.SessionFactory;
import org.hibernate.Transaction;
import org.hibernate.cfg.Configuration;

public class BaseDAOImpl implements BaseDAO {
    private SessionFactory sessionFactory;
    private Session session;
    private Transaction tx;
    public void init(){
        session = HibernateSessionFactory.getSession();
        tx = session.beginTransaction();
    }
    @Override
    public Session getSession() {
        init();
        return session;
    }
    @Override
    public void closeSession() {
        session.close();
    }
    @Override
    public List search(String hql) {
        Session session = null;
        session = getSession();
        List alist = null;
        alist = session.createQuery(hql).list();
        session.close();
        return alist;
    }
}
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
package njtech.edu.DAO.impl;


import njtech.edu.model.Student;
import njtech.edu.DAO.StudentDAO;
import org.hibernate.*;
import org.hibernate.cfg.Configuration;
import org.hibernate.criterion.Restrictions;

import java.util.List;

public class StudentDAOImpl extends BaseDAOImpl implements StudentDAO{
    SessionFactory sessionFactory = null;
    Session session = null;
    Transaction tx = null;
    public StudentDAOImpl(){}
    public void init() {
        sessionFactory = new Configuration().
                configure("hibernate.cfg.xml").
                buildSessionFactory();
        session = sessionFactory.openSession();
        tx = session.beginTransaction();
    }
    @Override
    public void saveStudent(Student student) {
        init();
        session.save(student);
        String sql = "insert into student (id,name,address) values('" +
                    Integer.toString(student.getId()) +".'"+
                    student.getName()+"','"+
                    student.getAddress()+"')"
                ;
        tx.commit();
        session.close();
    }

    @Override
    public List<Student> getAll() {
        init();
        List<Student> students = session.createQuery("from Student").list();

        //List<Student> students  = (Student) session.createQuery("from Student ");
        return students;
    }
    @Override
    public void changeStudent(Student student){
        init();
        Student student1 = (Student) session.get(Student.class, new Integer(student.getId()));
        // hql 查询
        //Student student2 = (Student) session.createQuery("from Student where id="+student.getId());
        // sql 查询
        //Query query = session.createSQLQuery("select * from student where id="+student.getId()).addEntity(Student.class);
        //Student student3 = (Student) query.list();
        student1.setName(student.getName());
        student1.setAddress(student.getAddress());
        session.update(student1);
        tx.commit();
        session.close();
    }
    @Override
    public void deleteStudent(Student student){
        init();
        Student student1 = (Student) session.get(Student.class, student.getId());
        // hql查询
        //Student student2 = (Student) session.createQuery("from Student where id="+student.getId());
        // sql 查询
        //Query query = session.createSQLQuery("select * from student where id="+student.getId()).addEntity(Student.class);
        //Student student3 = (Student) query.list();
        if(student  != null){
            session.delete(student1);
        }
        tx.commit();
        session.close();
    }
    @Override
    public List<Student> queryStudent(Student student){
        init();
        Criteria criteria
                = session.createCriteria(Student.class).add(Restrictions.like("id",student.getId()));
        //hql 查询
        Query query = session.createQuery("from Student where id="+student.getId());
        // sql 查询
        //Query query = session.createSQLQuery("select * from student where id="+student.getId()).addEntity(Student.class);
        //List<Student> students2 = query.list();
        List<Student> students = criteria.list();
        //return students2;
       return students;
    }
}

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
package njtech.edu.DAO.impl;

import njtech.edu.DAO.UserDAO;
import njtech.edu.model.Student;
import njtech.edu.model.User;
import org.hibernate.*;
import org.hibernate.cfg.Configuration;
import org.hibernate.criterion.Restrictions;

import java.util.List;

public class UserDAOImpl extends BaseDAOImpl implements UserDAO {
    SessionFactory sessionFactory = null;
    Session session = null;
    Transaction tx = null;
    public UserDAOImpl(){}
    public void init() {
        sessionFactory = new Configuration().
                configure("hibernate.cfg.xml").
                buildSessionFactory();
        session = sessionFactory.openSession();
        tx = session.beginTransaction();
    }
    @Override
    public User queryUser(String username) {
        init();
        Criteria criteria
                = session.createCriteria(User.class).add(Restrictions.like("username",username));

        User user = (User)criteria.uniqueResult();

        return user;
    }
}

action类代码

![image-20181128193156432](/Users/cheasim/Library/Application Support/typora-user-images/image-20181128193156432.png)

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
package njtech.edu.Action;

import java.util.ArrayList;
import java.util.List;
import java.util.regex.Pattern;

import com.opensymphony.xwork2.ActionSupport;
import com.opensymphony.xwork2.ModelDriven;
import njtech.edu.DAO.StudentDAO;
import njtech.edu.DAO.impl.StudentDAOImpl;
import njtech.edu.model.Student;

public class StudentAction extends ActionSupport implements ModelDriven {
    private Student student;
    private List<Student> students = new ArrayList<Student>();
    private StudentDAO dao = new StudentDAOImpl();
    public Object getModel() {
        return student;
    }
    public String saveStudent()
    {
        dao.saveStudent(student);
        return "success";
    }
    public String listStudents()
    {
        students = dao.getAll();
        return "success";
    }
    public String queryStudents(){
        students = dao.queryStudent(student);
        return "success";
    }
    public String changeStudent()
    {
        dao.changeStudent(student);
        return "success";
    }
    public String deleteStudent(){
        dao.deleteStudent(student);
        return "success";
    }
    public void validate(){
        System.out.println("校验器!");
    }
    public void validateSaveStudent(){
        if(student != null){
            Integer ID = student.getId();
            String IID = ID.toString();
            if("".equals(this.student.getName().trim())){
                this.addFieldError("username", "用户名不能为空");
            }
            if("".equals(this.student.getAddress().trim())){
                this.addFieldError("address", "地址不能为空");
            }
            if(!Pattern.compile("^(0|[1-9][0-9]*)$").matcher(IID).matches()){
                this.addFieldError("id", "ID格式不正确");
            }

        }
        super.validate();
    }
    public Student getStudent() {
        return student;
    }
    public void setStudent(Student student) {
        this.student = student;
    }
    public List<Student> getStudents() {
        return students;
    }
    public void setStudents(List<Student> students) {
        this.students = students;
    }
}
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
package njtech.edu.Action;

import com.opensymphony.xwork2.ActionSupport;
import com.opensymphony.xwork2.ModelDriven;
import njtech.edu.DAO.impl.UserDAOImpl;
import njtech.edu.model.User;

public class UserLoginAction extends ActionSupport {

    private User user;
    private UserDAOImpl dao= new UserDAOImpl();

    public String userLogin(){
        User tempuser = dao.queryUser(user.getUsername());
        if(tempuser.equals(user)){
            return "success";
        }else{
            return "error";
        }
    }
    public User getUser() {
        return user;
    }

    public void setUser(User user) {
        this.user = user;
    }


}

Hibernate配置文件

cfg.xml

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
<?xml version='1.0' encoding='utf-8'?>
<!DOCTYPE hibernate-configuration PUBLIC
        "-//Hibernate/Hibernate Configuration DTD//EN"
        "http://www.hibernate.org/dtd/hibernate-configuration-3.0.dtd">
<hibernate-configuration>
    <session-factory>
        <property name="connection.url">jdbc:mysql://localhost:3306/test?useSSL=false</property>
        <property name="connection.driver_class">com.mysql.jdbc.Driver</property>
        <property name="connection.username">root</property>
        <property name="connection.password">123456</property>
        <property name="current_session_context_class">thread</property>
        <property name="show_sql">true</property>
        <property name="hbm2ddl.auto">update</property>
        <property name="dialect">org.hibernate.dialect.MySQLDialect</property>
        <mapping class="njtech.edu.model.Student"/>
        <mapping resource="njtech/edu/model/Student.hbm.xml"/>
        <mapping resource="njtech/edu/model/User.hbm.xml"/>
    </session-factory>
</hibernate-configuration>

hbm user和student

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
<?xml version='1.0' encoding='utf-8'?>
<!DOCTYPE hibernate-mapping PUBLIC
    "-//Hibernate/Hibernate Mapping DTD 3.0//EN"
    "http://www.hibernate.org/dtd/hibernate-mapping-3.0.dtd">
<hibernate-mapping>

    <class name="njtech.edu.model.Student" table="student" schema="test">
        <id name="id">
            <column name="id" sql-type="int(11)"/>
        </id>
        <property name="name">
            <column name="name" sql-type="varchar(100)" length="100" not-null="true"/>
        </property>
        <property name="address">
            <column name="address" sql-type="varchar(100)" length="100" not-null="true"/>
        </property>
    </class>
</hibernate-mapping>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
<?xml version='1.0' encoding='utf-8'?>
<!DOCTYPE hibernate-mapping PUBLIC
    "-//Hibernate/Hibernate Mapping DTD 3.0//EN"
    "http://www.hibernate.org/dtd/hibernate-mapping-3.0.dtd">
<hibernate-mapping>

    <class name="njtech.edu.model.User" table="user" schema="test">
        <id name="username">
            <column name="username" sql-type="varchar(20)" length="20"/>
        </id>
        <property name="password">
            <column name="password" sql-type="varchar(20)" length="20"/>
        </property>
    </class>
</hibernate-mapping>

model类 Student User

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
package njtech.edu.model;

import javax.persistence.*;
import java.util.Objects;
public class Student {
    private int id;
    private String name;
    private String address;
    public Student(){}
    public Student(int id, String name, String address){
        this.id = id;
        this.name = name;
        this.address = address;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getAddress() {
        return address;
    }

    public void setAddress(String address) {
        this.address = address;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student that = (Student) o;
        return id == that.id &&
                Objects.equals(name, that.name) &&
                Objects.equals(address, that.address);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id, name, address);
    }
}

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
package njtech.edu.model;

import java.util.Objects;

public class User {
    private String username;
    private String password;
    public User(){}
    public String getUsername() {
        return username;
    }

    public void setUsername(String username) {
        this.username = username;
    }

    public String getPassword() {
        return password;
    }

    public void setPassword(String password) {
        this.password = password;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        User user = (User) o;
        return Objects.equals(username, user.username) &&
                Objects.equals(password, user.password);
    }

    @Override
    public int hashCode() {
        return Objects.hash(username, password);
    }
}

Struts2配置文件

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
<?xml version="1.0" encoding="UTF-8"?>

<!DOCTYPE struts PUBLIC
        "-//Apache Software Foundation//DTD Struts Configuration 2.3//EN"
        "http://struts.apache.org/dtds/struts-2.3.dtd">

<struts>
    <package name="default" extends="struts-default">
        <action name="addStudent" method="saveStudent"
                class="njtech.edu.Action.StudentAction">
            <result name="success" type="redirect">
                listStudents.action
            </result>
            <result name="input">add.jsp</result>
        </action>
        <action name="changeStudent" method="changeStudent"
                class="njtech.edu.Action.StudentAction">
            <result name="success" type="redirect">
                listStudents.action
            </result>
        </action>
        <action name="listStudents" method="listStudents"
                class="njtech.edu.Action.StudentAction">
            <result name="success">
                index.jsp
            </result>
        </action>
        <action name="queryStudents" method="queryStudents"
                class="njtech.edu.Action.StudentAction">
            <result name="success" >
                queryStudent.jsp
            </result>
        </action>
        <action name="deleteStudent" method="deleteStudent"
                class="njtech.edu.Action.StudentAction">
            <result name="success">
                success.jsp
            </result>
        </action>
        <action name="userLogin" method="userLogin"
                class="njtech.edu.Action.UserLoginAction">
            <result name="success"> index.jsp</result>
            <result name="error">login.jsp</result>
        </action>
    </package>
</struts>

前端代码

css

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
body
{
    background: url("../image/2.jpg") no-repeat;
    background-size:100%;
    background-attachment: fixed;
}
form{
    display:inline-block;
    margin-top:100px;
}
h1
{
    color: #ffb11c;
    text-align:center;
}
p
{
    font-family:"Times New Roman";
    font-size:20px;
}
table
{
    border-collapse:collapse;
}
table,th, td
{
    border: 0px solid black;
    border-bottom-color: aqua;
}
form
{
    background:rgba(255,255,255,0.3);
    border: 1px solid rgba(0,0,0, 0.2);
    font-family:"Monaco";
    font-size: 40px;
    border-radius: 30px;
}
.input_control{
    width:360px;
    margin:14px auto;
}
.error_message{
    color: #ff383f;
    font-size: 20px;
}
input[type="text"]{
    box-sizing: border-box;
    text-align:center;
    font-size:1.0em;
    height:2.0em;
    border-radius:20px;
    border:1px solid #c8cccf;
    color:#6a6f77;
    -web-kit-appearance:none;
    -moz-appearance: none;
    display:block;
    outline:0;
    padding:0 1em;
    text-decoration:none;
    width:100%;
}
input[type="password"]{
    box-sizing: border-box;
    text-align:center;
    font-size:1.0em;
    height:2.0em;
    border-radius:20px;
    border:1px solid #c8cccf;
    color:#6a6f77;
    -web-kit-appearance:none;
    -moz-appearance: none;
    display:block;
    outline:0;
    padding:0 1em;
    text-decoration:none;
    width:100%;
}
input[type="text"]:focus{
    border:1px solid #ff7496;
}
.button{
    background-color: #af8c99; /* Green */
    border: none;
    color: white;
    padding: 17px 28px;
    text-align: center;
    text-decoration: none;
    display: inline-block;
    font-size: 14px;
    border-radius:4px;
}

JSP

第一个页面

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
<%--
  Created by IntelliJ IDEA.
  User: cheasim
  Date: 2018/11/11
  Time: 11:57 AM
  To change this template use File | Settings | File Templates.
--%>
<%@ page contentType="text/html;charset=UTF-8" language="java" %>
<%@taglib prefix="s" uri="/struts-tags"%>
<html>

<head>
    <title>登陆界面</title>
    <link type="text/css" rel="stylesheet" href="css/mystyle.css"/>
    <style>
        <!--
        form{ height:350px; width:400px; border:1px solid #666666;}
        -->
    </style>
    <script type="text/javascript">
        function login(){
            document.myform.action='http://localhost:8080/userLogin.action';
            document.myform.submit();
        }
    </script>
    <style type="text/css">
        .button{
            background-color: #af8c99; /* Green */
            border: none;
            color: white;
            padding: 14px 28px;
            text-align: center;
            text-decoration: none;
            display: inline-block;
            font-size: 20px;
            border-radius:13px;
        }
    </style>
</head>
<body>
<center>
<h1> 管理员登陆界面</h1>
<form action="userLogin" name="myform">
    <s:textfield name="user.username" label="用户名"/>
    <s:textfield name="user.password" label="密码" type="password"/>
    <input type="button" class="button" value="登陆" onclick="login();" align="right"/>
</form>
</center>
</body>
</html>

选择页面

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
<%@ page contentType="text/html; charset=UTF-8"%>
<%@ taglib prefix="s" uri="/struts-tags"%>
<html>
<head>
  <title>学生登录系统</title>
  <link type="text/css" rel="stylesheet" href="css/mystyle.css" />
    <style type="text/css">
        .button{
            background-color: #af8c99; /* Green */
            border: none;
            color: white;
            padding: 15px 30px;
            text-align: center;
            text-decoration: none;
            display: inline-block;
            font-size: 24px;
            border-radius:13px;
        }
    </style>
    <script type="text/javascript">
        function goAdd(){
            document.myform.action='add.jsp';
            document.myform.submit();
        }
        function goDelete(){
            document.myform.action='queryStudent.jsp';
            document.myform.submit();
        }
    </script>
</head>
<body>
<center>
<h1>学生系统学生一览</h1>
    <form name="myform">
        <table>
            <tr>
                <input type="button" class="button" value="增加和修改" onclick="goAdd();"/>
            </tr>
            <tr>
                <input type="button" class="button" value="删除和查询" onclick="goDelete();"/>
            </tr>

        </table>
    </form>
<s:if test="students.size() > 0">
  <table border="1px" cellpadding="8px" bgcolor=#faebd7 style="filter:alpha(opacity=50);">
    <tr>
      <th>Student Id</th>
      <th>Name</th>
      <th>Address</th>
    </tr>
    <s:iterator value="students">
      <tr>
        <td><s:property value="id" /></td>
        <td><s:property value="name" /></td>
        <td><s:property value="address" /></td></td>
      </tr>
    </s:iterator>
  </table>
</s:if>
</center>
</body>
</html>

增加和修改

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
<%--
  Created by IntelliJ IDEA.
  User: cheasim
  Date: 2018/11/28
  Time: 3:39 PM
  To change this template use File | Settings | File Templates.
--%>
<%@ page contentType="text/html;charset=UTF-8" language="java" %>
<%@ taglib prefix="s" uri="/struts-tags"%>
<html>
<head>
    <title>增加学生</title>
    <link type="text/css" rel="stylesheet" href="css/mystyle.css" />
    <script type="text/javascript">
        function changeStudent(){
            document.myform.action='http://localhost:8080/changeStudent.action';
            document.myform.submit();
        }
        function saveStudent(){
            document.myform.action='http://localhost:8080/addStudent.action';
            document.myform.submit();
        }
    </script>

</head>
<body>
<center>
    <form action="addStudent" name="myform">
        <h4> 加入学生信息</h4>
        <s:textfield name="student.id" label="ID"/>
        <s:fielderror fieldName="id" cssClass="error_message"/>
        <s:textfield name="student.name" label="Name"/>
        <s:fielderror fieldName="username" cssClass="error_message"/>
        <s:textfield name="student.address" label="Address"/>
        <s:fielderror fieldName="address" cssClass="error_message"/>
        <input type="button" class="button" value="改变" onclick="changeStudent();"/>
        <input type="button" class="button" value="增加" onclick="saveStudent();"/>
    </form>
</center>
</body>
</html>

查询和删除

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
<%--
  Created by IntelliJ IDEA.
  User: cheasim
  Date: 2018/11/14
  Time: 2:43 PM
  To change this template use File | Settings | File Templates.
--%>
<%@ page contentType="text/html;charset=UTF-8" language="java" %>
<%@ taglib prefix="s" uri="/struts-tags"%>
<html>
<head>
    <title>查询结果</title>
    <link type="text/css" rel="stylesheet" href="css/mystyle.css" />
    <script type="text/javascript">
        function deleteStudent(){
            document.myform1.action='http://localhost:8080/deleteStudent.action';
            document.myform1.submit();
        }
        function queryStudent(){
            document.myform1.action='http://localhost:8080/queryStudents.action';
            document.myform1.submit();
        }
    </script>
</head>
<body>
<center>
    <form action="queryStudents" name="myform1">
        <h4> 查询学生信息
            依据id搜索或者删除</h4>
        <s:textfield name="student.id" label="ID"/>
        <input type="button" class="button"value="删除" onclick="deleteStudent();"/>
        <input type="button"class="button" value="查询" onclick="queryStudent();"/>
    </form>
<h1>学生查询结果</h1>
<s:if test="students.size() > 0">
    <table border="1px" cellpadding="8px" bgcolor=#faebd7 style="filter:alpha(opacity=50);">
        <tr>
            <th>Student Id</th>
            <th>Name</th>
            <th>Address</th>
        </tr>
        <s:iterator value="students">
            <tr>
                <td><s:property value="id" /></td>
                <td><s:property value="name" /></td>
                <td><s:property value="address" /></td></td>
            </tr>
        </s:iterator>
    </table>
</s:if>
</center>
</body>
</html>

发表更新acm3 分钟读完 (大约510个字)

[hdoj5559]Frog and String

Frog and String

题意

给定一个字符串的长度和他里面子回文串的个数。

  • 子回文串是连续子串，并且相同的回文串不重复计数
  • 字符串由前$K$个字符构成

题解

构造题嘛，最重要的就是规律啦。

对于构造题，我们就要一步一步来，把题目分段。

  1. 首先对于$K=1$来说，如果$n !=m$的话，无解。
  2. 对于$K=2$来说，这时候爆搜就起作用了，我怎么想也不肯能根据我那只有6长度的字符串想到会存在一个长度为8但是只有7个自回文串的字符串。他就是$AABABBAA$.估计只有搜才能发现这个玩意，之后就会发现只有两个字符，你也能构造一个长度很长，但只有很少的子回文串。$AABABB$这个玩意可以无限重复，但是只有$A,B,AA,BB,ABA,BAB,ABBA,BAAB$这四种玩意。
  3. 对于$K \ge 3$，最好想，就是$ABC$来重复计数，$m-3$个前导$A$

我真是蠢，真的，没有去用爆搜找一下答案，就凭自己的直觉在那里搞来搞去。

+1 $m=2$的时候少考虑了

+1 当$k>m$的时候

+1 单独测试用例 没有print case

+1 特判m==n没有加else if

+1 $k=2,n=m$的时候出现了错误。应该特判的。

ac代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 1e5+10;
const int maxk = 30;
int n,k,m;
char magic[10] = "ABAABB";
int main(){
#ifdef LOCAL
    freopen("1.in","r",stdin);
#endif
    int T; scanf("%d",&T);
    rep(test_case,1,T+1){
        scanf("%d%d%d",&n,&m,&k);
        bool flag = false;
        if(n!=m){
            if(k==1) flag = true;
            if(k==2 && m<8) flag = true;
            if(k>=3 && m<=2) flag = true;
            if(n<m) flag = true;
            if(m==7 && n==8 && k==2){
                printf("Case #%d:\n",test_case);
                puts("AABABBAA");
                continue;
            }
        }
        printf("Case #%d:\n",test_case);
        if(flag) puts("Impossible");
        else if(n==m){
            rep(i,0,n) printf("A");
            puts("");
        }else if(k==2){
            int cnt = m-8;
            rep(i,0,cnt) printf("A");
            rep(i,0,n-cnt) printf("%c",magic[i%6]);
            puts("");
        }else{
            vector<char> ve;
            rep(i,0,m-3) printf("A");
            rep(i,0,3) ve.push_back('A'+i);
            rep(i,0,n-m+3){
                printf("%c",ve[i%3]);
            }
            puts("");
        }
    }
    return 0;
}
发表更新html几秒读完 (大约10个字)

html5学习笔记

html5学习笔记

功能很强。

发表更新开发几秒读完 (大约66个字)

iBatis框架 粗略学习

iBatis

jar包

  • Ibatis 2.3.4
  • Sql server

配置文件

配置文件和Hibernate类似

映射文件

他的映射方式是把CRUD映射到操作。

1
2
3
<insert id="insertStudent" parameterClass="Student">
	...
</insert>

初始化

1
2
3
inputStream ins = Resources.getResourceAsStream("sql-map-confg.xml");
client = SqlMapClientBuilder.buildSqlClient(ins);
Client.startTransaction();

老师不讲了，溜了溜了

关注我

链接

分类

最新文章

归档

标签

AI2
LCA1
Linux1
QA1
acm13
ac自动机1
ajax1
bert1
bilstm1
cf8
colab1
crf1
css1
dfs3
dgl1
dp5
dptree1
echarts1
gnn1
graph1
greedy1
hash2
hdoj1
html1
js1
jsp1
lca1
linux1
math1
matrix1
nlp2
pat2
pytorch1
re1
struts21
tokenizer1
web1
专题1
二分1
人生1
保研1
八数码1
图论1
字符串1
字符串hash1
学习笔记6
学习计划1
小技巧1
开发3
抽取1
数学1
数据结构1
最大子段和1
构造1
树形dp5
树状数组2
树状数组，hdoj1
树链剖分1
概率dp1
模拟1
模板1
爆搜1
牛客网1
状压dp1
线段树6
组合数学1
细节1
缩点1
网络1
网络赛3
考研2
范围1
蓝桥杯2
补题1
规律1
计划1
计算几何1
论解2
贪心7
递归1
配置1
随性1
预处理1

订阅更新

You need to set client_id and slot_id to show this AD unit. Please set it in _config.yml.
×