小L的项链切割

Description:
题目描述
小T送给了小L了一串项链。为了方便，我们把项链上形态不同钻石用不同的字母表示。这样小L的项链就变成了一个字符串。小L忽然想把这串项链优美地切割一下，她想把它切割成尽量少的回文项链，啊也就是回文串。求最少的切割次数。
输入
第一行一个整数T 表示数据组数
下面T组数据，每一组数据:
只有一行，一个只有小写英文字母的字符串，字符串长度 <= 1000。
输出
对于每一组数据，输出将这个字符串能切割成最少的回文串所需切割的次数。
样例输入
2
abaacca
abcd
样例输出
1
3
Problem solving:
这道题毫无思路，据说是个dp，会了再补。

Code:

#include<iostream>
#include<vector>
using namespace std;    
 bool IsPalindRome(string str){//回文判断
        int end=str.length()-1;
        int start=0;
        while(start<end){
            if(str[start]==str[end]){
                start++;
                end--;
            }else{
                return false;
            }
        }
        return true;
    }
    int minCut(string s) {
        int len=s.length();
        vector<int> dp(len,0);//初始化为0
        for(int i=0;i<len;i++){
            dp[i]=IsPalindRome(s.substr(0,i+1)) ? 0 : i;//初始化
            if(dp[i]==0)
                continue;
            else{
                for(int j=1;j<=i;j++){
                    if(IsPalindRome(s.substr(j,i-j+1)))
                        dp[i]=min(dp[i],dp[j-1]+1);
                    else{
                        dp[i]=min(dp[i],dp[j-1]+i-j+1);
                    }
                }
            }
        }
        return dp[len-1];
    }

int main(){
    string str;
    int n;
    cin>>n;
    while(n--){
        cin>>str;
        cout<<minCut(str)<<endl;
    }
}

代码来自：weixin_30953169

小L的试卷

Description:
小L期末考试结束，高高兴兴放假回家了，可是那么多试卷，老师还要加班批改，有n份试卷由k个老师批改，n份试卷进行了密封编号，由于试卷上的做题情况和书写的规范程序不一样，批改不同的试卷用时也可能不一样，每个老师批改试卷的编号顺序是连续的，每位老师批改完分配给自己的试卷就可以离开，问最后离开的老师，最短可能的用时是多少，假定一份试卷让任何一位老师批改用时都是一样的。现在请你设计一种分配方案，使得最后离开的老师用时最短。
输入
第一行两个整数n，k；（0<k≤n≤1000）
第二行n个整数，第i个整数表示批改第i份试卷的用时。
输出
输出一个整数，表示最后离开的老师所用的最短时间
样例输入
9 3
1 2 3 4 5 6 7 8 9
样例输出
17
Problem solving:
这道题的意思就是有k个老师在改卷子。每张卷子耗费的时间都是不一样的，问你怎么分卷子给老师可以让最晚走的老师的时间是最早的。
这道题当时是真的是毫无思路，根本没有想到可以用二分写。。。其实想到最晚的最早就该能想到二分的。
难点就是在二分中间的判断，这道题要求的是每个老师改的卷子的序号是相邻的，所以直接找最大值看跟要判断的值得大小关系就行啦。
二分函数中可以直接从第一个卷子开始加，然后如果当前累加的值大于了要判断的值，就让总人数加一。不是很好说这里，看代码注释、
Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f3f;
const int maxn = 1e5+10;
int n,k;
ll a[maxn];
bool isok(int x)//判断x是否满足条件
{
    int flag=0;
    int num=0;ll temp=0;//num就是需要的改卷老师的人数
    for(int i=0;i<n;i++)
    {
        if(a[i]>x)    return 0;//如果有一张卷子自己一张的时间已经大于当前要判断的值，说明x不满足条件。直接返回0
        temp+=a[i];//这个累加的是第num个老师所需要的时间
        if(temp>x)//如果所需要的时间大于当前要判断的值。
        {
            num++;就在多一个老师，
            temp=a[i];并且把当前这张卷子归给下一个老师
        }
    }
    if(temp>0)    num++;//这个处理必须要有，因为你有可能全部加起来的时间还没到达这个x，但此时老师个数还是要加一的
    if(num<=k)    return 1; //如果需要的老师人数小于k说明这个值满足条件，返回1
    else    return 0;
}
int main()
{
    cin>>n>>k;
    for(int i=0;i<n;i++)    cin>>a[i];
    ll l=0,r=INF;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(isok(mid))    r=mid-1;
        else    l=mid+1;
    }
    cout<<l<<endl;
    return 0;
}

这道题现在看来当时写不出来也太亏了，二分这个思想还是掌握的不够熟练啊！

小L记单词

Description:
小L最近在努力学习英语，但是对一些词组总是记不住，小L小把这些词组中每一个单词的首字母都记一下，这样形成词组的缩写，通过这种方式小L的学习效率明显提高。
输入
输入有多行，每组测试数据占一行，每行有一个词组，每个词组由一个或多个单词组成；每组的单词个数不超过10个，每个单词由大、小写字母组成；
单词长度不超过10，由一个空格分隔这些单词。
输出
对应每一个词组，输出词组的缩写，缩写都用大写字母，每组输出占一行。
样例输入
end of file
样例输出
EOF
Problem solving:
这是一道签到题，就是给你几串字符串，让你输出字符串中每个单词的首字母的大写形式。
用getline输入，然后判断前一个是不是空格，如果是，输出大写形式就行了。
Code:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    while(getline(cin,s))
    {
        if(s[0]>='a'&&s[0]<='z')
            printf("%c",s[0]-32);
        else
            cout<<s[0];
        for(int i=1;i<s.size();i++)
        {
            if(s[i-1]==' ')
            {
                if(s[i]>='a'&&s[i]<='z')
                    printf("%c",s[i]-32);
                else
                    cout<<s[i];
            }
        }
        puts("");
    }
}

小L的取膜算式

Description:
小L想请你帮忙计算一下这个式子的结果
(a+b)^p MOD p，其中p是质数。
输入
多组数据
第一行一个T表示数据组数
接下来T行，每行3个正整数a, b, p且保证p是质数 ，输入数据都是long long范围内的正整数。特别的: p <= 2^62
输出
对于每一组输入数据，输出正确结果
样例输入
1
1 2 3
样例输出
0
提示
注意p是质数，结合二项式定理可以很容易推得一个结论但是不一定能在时限内通过本题，但稍微再往后推一下就会发现一个非常优美的结论并AC此题
输入数据都是long long范围内的正整数。特别的: p <= 2^62
Problem solving:
这道题就是给你三个数，a,b,p,让你输出(a+b)的p次方对p取模的结果。
一开始想着用快速幂，但是不知道为啥会WA。然后就看到了提示，非常优美的结论，我突然就想到了我们学长卡我们的时候的丑恶意味深长的笑容。然后就想着直接输出(a+b)对p取模的结果，wa了一次，因为a+b可能爆long long，所以要先取模再相加再取模。。。这道题坑的也是够可以。

现在我知道了，因为费马小定理可以得到(a^(p-1))%p=1,所以我们可以将((a+b)^p)%p化简成((a+b)^(p-1))%p*((a+b)%p)，前半部分为1，所以答案就是(a+b)%p

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,a,b,p;
int main()
{
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld %lld %lld",&a,&b,&p);
        printf("%lld\n",(a%p+b%p)%p);
    }
}

小L玩滚球游戏

Description:
小L正在玩滚球游戏，有n个水晶球在轨道上以不同开始位置和速度从近往远的方向滚动，如果两个水晶球在滚动过程中相遇，它们就会融合成一个水晶球，然后以速度较慢的水晶球的速度继续向前滚动， 问经过时间t后，轨道上还有多少水晶球。
输入
第一行输入两个整数n、t，n代表水晶球的数量（1 <= n <= 1e5, 0<t<2^31），t代表时间。
接下来n行，每行两个整数，按位置从近到远的顺序给出水晶球的初始位置和速度。
输出
输出一个整数表示经过时间t后水晶球的数量。
样例输入
5 3
0 1
1 2
2 3
3 2
6 1
样例输出
3
Problem solving:
这个题的意思就是给你n个小球，还给出了他们的初始位置以及速度。问你在t秒后还剩几个小球。如果在运动过程中有两个小球撞在一起了，那么他俩就以他俩的最小速度继续走下去。
我以为这个题是模拟。但是也没模拟出来

其实这个可以这样
根据题意，移动速度快的球可能会追上在他前面移动速度慢的球，并且追上后合并在一起会变成前面速度慢的球。
可以将题意理解为，后面移动速度快的球碰到前面移动速度慢的球则会消失。
而且t是固定的值，直接计算每个位置在t秒后移动到的位置，逆向维护一个最靠后的值，检测当前球是否超过这个值。
如果超过则说明追上了后面的球当前球会消失。
题解转载于： CaprYang

原来是个思维的问题
Code:

#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int maxn  =  1e5+10;
ll a[maxn],b[maxn];
int main()
{
    int n,t,m=0;
    cin>>n>>t;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i]>>b[i];
        a[i]+=b[i]*t;
    }
    ll mid=INF;
    for(int i=n;i>0;i--)
    {
        if(a[i]>=mid)    m++;
        mid=min(mid,a[i]);
    }
    cout<<n-m<<endl;
    return 0;
}

小L的区间求和

Description:
在给定的一个整数序列中，小L希望找到一个连续的区间，这个区间的和能够被k整除，请你帮小L算一下满足条件的最长的区间长度是多少。
输入
第一行输入两个整数n、k。（1 <= n <= 1e5,1<=k<100）
接下来一行输入n个整数，表示序列中的数。
输出
输出一个整数，满足条件区间的最长长度，如果不存在，输出0
样例输入
5 7
1 2 4 1 1
样例输出
3
Problem solving:
这道题就是给你一个序列，如果存在连续的几个数的和能整除k，求出这个连续的序列的最大的长度。

一开始没思路，又想到了前缀后缀和数组，最后用了暴力都没过。然后我就想到了这样写。出现k的倍数范围太大，可以输入的时候用一个前缀和数组并且对k取模。然后我们只需要在一个for循环查找是否有取模之后结果相等的两个值。如果有就说明这之间数的和是k的倍数。

举个栗子

3 10
3%7=3 == 10%3=7
(10-3)%7==0

所以我们只需要每次找到取模之后的前缀和相等的两个位置的最大值就是答案

Code:

#include <bits/stdc++.h>
using namespace std;
int a[100005], s[100005];
map<int, int> ma;
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for(int i=1; i<=n; i++)
    {
        scanf("%d", &a[i]);
        s[i] = (s[i-1]+a[i])%k;
        ma[s[i]] = -1;
    }
    int ans = 0;
    ma[s[0]] = 0;
    for(int i=1; i<=n; i++)
    {
        if(ma[s[i]] == -1)
        {
            ma[s[i]] = i;
        }
        else
        {
            ans = max(ans, i-ma[s[i]]);
        }
    }
    printf("%d\n", ans);
    return 0;
}

小L的随机数

Description:
随机数是生成随机算法的基础，小L准备使用线性同余法（Linear Congruential Method）来生成一个随机数列，这种方法需要设置四个非负整数参数m, a, c, x0按照下面的公式生成出一系列随机数 : Xn+1 = (a * Xn + c) mod m ,小L现在想知道这个数列第n个数是多少，由于他只需要生成小于g的随机数，所以你只需要告诉他Xn mod g的结果即可。
输入
输入一行6个整数，分别表示m, a, c, X0, n, g 。(n ≤ 1e6，1 ≤ m, a, c, X0 , g ≤2^31 − 1)
输出
一行一个整数表示Xn
样例输入
233 3 3 3 3 333
样例输出
120
Problem solving:
这道题给了你一个递推式以及第一项的值，问你第n项的值对g取模的结果。

这道题挺简单的，直接暴力就可以过。
Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll m,a,c,xo,x[1000005],n,g;
int main()
{
    cin>>m>>a>>c>>xo>>n>>g;
    ll ans=xo;
    for(int i=1;i<=n;i++)
    {
        ans=(a*ans+c)%m;
    }
    cout<<ans%g<<endl;
}

小L的直线

Description:
小学时期的小L发现自己很有艺术细胞，于是买了一块画板，但是他的绘画水平使得他只能连接两点画出一条线段。有一天他决定在一张有n个点的图上作画，即他可以把这n个点任意连接。大家认为平行线是非常不美观的，于是他想知道自己最多能画多少条直线使整张画不出现平行线。
输入
第一行输入一个整数n （1 <= n <= 200）
接下来n行每行两个整数代表每个点的坐标x, y （-1000 <= x, y <= 1000）
输出
一行一个整数为能画出最多的两两不平行的直线条数
样例输入
4
-1 1
-2 0
0 0
1 1
样例输出
4
Problem solving:
这道题就是给你n个点，问你最多构成几条没有平行情况出现的直线。

数据范围不大，直接暴力计算每条直线的斜率，得出不同斜率的个数就是答案。

这道题跟之前积分赛有一道题很像，我还是用set套pair做的，不知道直接算斜率会不会卡精度。不过还是直接用pair表示斜率来得舒服，注意存的时候要进行约分。

Code:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 521;
int x[maxn],y[maxn];
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>x[i]>>y[i];
    set<pair<int,int> > se;
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            int m=x[i]-x[j],mm=y[i]-y[j];
            int gg=__gcd(m,mm);
            if(gg!=0)
                m/=gg,mm/=gg;
            se.insert(make_pair(m,mm));
        }
    }
    cout<<se.size()<<endl;
}

小L的长方形

Description:
在数学课上，老师发给小L一根铁丝，让小L将这根铁丝围成一个长方形。要求这个长方形的长是宽的3倍，并且计算它的面积。
输入
仅一个整数a，表示铁丝的长度(a≤10000)。
输出
输出三个数，分别表示长方形的长、宽、面积。如果计算结果是整数，则输出整数结果（没有小数部分）；如果不是，则保留三位小数。每个数之间用一个空格隔开。
样例输入
36
样例输出
13.500 4.500 60.750
Problem solving:
这道题就是给了你一个长方形的周长以及它的长和宽的关系，问你它的面积。

周长除了8就是宽，宽乘以3就是长，长乘宽就是面积。
有一个需要注意的地方是他的输出，题目要求如果是整数就不输出小数部分，否则保留三位小数。只需要判断长跟宽是不是整数就行，用一个ceil(向上取整)来判断就行.

Code:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    double a,b,c;
    cin>>a;
    b=a/8,c=b*3;
    if(ceil(b)==b&&ceil(c)==c)
    {
        printf("%.0lf %.0lf %.0lf",c,b,c*b);
    }
    else
    printf("%.3lf %.3lf %.3lf",c,b,c*b);
}

今天的题大多不难，就是思维问题。体验还是不错的。

赏