Fluctuation Limit
链接:http://acm.hdu.edu.cn/showproblem.php?pid=6860
这题刚开始我的思路是正确的,当时是想根据题目的限制条件推出每一天的可能范围,但后面在代码实现时不知道哪里想错了,就认为这个方法不可行。后面尝试dfs,预计会超时,稍稍试了一下剪枝之后还是不行,后面只好放弃了。
首先每一天要取股票可能的价格区间和预测价格的区间最小值;比如第i-1天股票价格可能为 [l,r] , 预测价格为 [L,R] 。那么第i天的股票价格范围就是:[ min(l-k,L) , min(r+k,R) ];根据这种递推关系,依次求出每一天的价格区间即可;输出价格的时候,可以从最后一天开始计算,依次取区间最大值,如果第i天取res,如果第i-1天的右端点>=res+k,那么第i-1天就取res+k,否则就取第i-1天的右端点即可;

#include<iostream>
#include<vector>
using namespace std;
const int N = 1e5+10;
int l[N],r[N];
int n,k;
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++){
            scanf("%d%d",&l[i],&r[i]);
        }
        vector<int> ve;
        bool flag=0;
        for(int i=2;i<=n;i++){
            l[i]=max(l[i],l[i-1]-k);
            r[i]=min(r[i],r[i-1]+k);
            if(l[i]>r[i]){
                flag=1;
                break;
            }
        } 
        if(flag){
            printf("NO\n");
            continue ; 
        }
        ve.push_back(l[n]);
        int la=l[n]-k,ra=l[n]+k;
        for(int i=n-1;i>=1;i--){
            l[i]=max(la,l[i]);
            r[i]=min(ra,r[i]);
            ve.push_back(l[i]);
            la=l[i]-k;
            ra=l[i]+k;
        }
        int len=ve.size();
        printf("YES\n");
        for(int i=len-1;i>=0;i--){
            printf("%d ",ve[i]);
        } 
        puts("");
    }
    return 0;
 } 

Isomorphic Strings
链接:http://acm.hdu.edu.cn/showproblem.php?pid=6863
这题如果hash用的比较熟的话,还是挺好做的。奈何我hash会点皮毛,而且当时想了两个角度,然后果断选了KMP/(ㄒoㄒ)/~~,毕竟KMP看了比较多。本身我的思维漏洞也挺多的,后面一一修正过来之后,还是T到怀疑人生。之前看好多人的代码时间差非常大,还有一点信心,但我的死活过不了。。。还是老老实实学好hash吧。

#include <algorithm>
#include <iostream>
#include <map>
#include<cstring>
#define ll long long
using namespace std;
const ll mod = 13331;
const double eps = 1e-6;
const ll inf = 0x3f3f3f3f;
const ll N = 5e6 + 10;
ll num[30],ha[N],p[N];
char s[N];
map<ll,ll> mp;
int main(){
    p[0]=1;
    for(ll i=1;i<N;i++)    p[i]=p[i-1]*mod;
    ll t;
    scanf("%lld",&t);
    while(t--){
        ll n;
        scanf("%lld",&n);
        scanf("%s",s+1);
        memset(num,0,sizeof(num));
        ha[0] = 0;
        for(ll i=1;i<=n;i++){
            num[s[i]-'a'+1]++;
            ha[i]=ha[i-1]*mod+(s[i]-'a'+1);
        }
        ll gg=n;
        for(ll i=1;i<=26;i++){
            if(num[i])    gg=__gcd(gg,num[i]);
        }
        ll u=n/gg;
        ll flag=1;
        if(u==1&&n!=1)    flag=0;
        else{
            for(ll i=1;i<gg;i++){
                ll len=i*u;
                if(n%len)    continue;
                flag= 0;
                mp.clear();
                LL k=ha[len]-ha[0]*p[len];
                mp[k]=1;
                for(ll j=1;j<len;j++){
                    k=k*mod+(s[j]-96);
                    mp[k-ha[j]*p[len]]=1;
                }
                for(ll j=1;j*len<=n;j++){
                    if (mp[ha[j*len]-ha[(j-1)*len]*p[len]]==0){
                        flag=1;
                        break;
                    }
                }
                if(flag==0)    break;
            }
        }
        if(flag==0)    printf("Yes\n");
        else    printf("No\n");
    }
    return 0;
}