这道题居然可以用string暴力A掉…… 提交记录 内网OJ

// luogu-judger-enable-o2
#include <iostream>
#include <string>
#include <regex>
int cursor;
int operations, operationValue, textLength;
std::string text, operationType, operationText, finalText;
char currentChar;
int main() {
    std::ios::sync_with_stdio(false);
    std::cin >> operations;
    while (operations--) {
        std::cin >> operationType;
        if (operationType == "Move") {
            std::cin >> operationValue;
            cursor = operationValue;
        } else if (operationType == "Insert") {
            std::cin >> operationValue;
            finalText = "";
            textLength = 0;
            while (std::cin.get(currentChar)) {
                if (currentChar < 32 || currentChar > 126 || currentChar == '\n' || currentChar == '\r')
                    continue;
                ++ textLength;
                finalText += currentChar;
                if (textLength >= operationValue)
                    break;
            }
            text.insert(cursor, finalText);
        } else if (operationType == "Delete") {
            std::cin >> operationValue;
            text.erase(cursor, operationValue);
        } else if (operationType == "Get") {
            std::cin >> operationValue;
            std::cout << text.substr(cursor, operationValue) << std::endl;
        } else if (operationType == "Prev") {
            if (cursor)
                --cursor;
        } else if (operationType == "Next") {
            if (cursor < text.length())
            ++cursor;
        }
    }
    return 0;
}

写了一个让Aviutl能通过midi生成PV的脚本,目前还在测试中。

只需要需要在Aviutl安装目录下的Scripts文件夹新建两个文件:

1. midi.obj

--file:

if not videoFile then
    videoFile = {file}
else
    obj.setfont("", "40")
    obj.load("text", "OK")
end

2. midi.anm

--dialog:Import alpha channel/chk, alpha=0;MIDI File, midiPath="";MIDI Track, midiTrack="";Flip horizontal/chk, flipH=1;Flip vertical/chk, flipV=0;Other effects, effects={};
function getByteValue(str, begin)
    local pos, value = begin, 0
    while string.byte(str, pos, pos) > 128 do
        value = value * 128 + string.byte(str, pos, pos) % 128
        pos = pos + 1
    end
    value = value * 128 + string.byte(str, pos, pos)
    pos = pos + 1
    return value, pos
end
function getValue(str, begin, last)
    local i, value = begin, 0
    while i <= last do
        value = value + string.byte(str, i, i) * 256 ^ (last-i)
        i = i + 1
    end
    return value
end
function parseMidi(filePath)
    -- Open midi file
    local midiFile = io.open(filePath, "rb")
    if midiFile == nil then
        obj.load("text", "The file does not exist")
        return false
    end
    -- Load content
    local midiContent = midiFile:read("*all")
    local midiContentLength = string.len(midiContent)
    if string.sub(midiContent, 1, 4) ~= "MThd" then
        obj.load("text", "This is not a midi file")
        midiFile:close()
        return false
    end
    -- Parse content
    midiType        = getValue(midiContent,  9, 10)
    midiTracksCount = getValue(midiContent, 11, 12)
    midiDeltaTime   = getValue(midiContent, 13, 14)
    notes           = {}

    -- Parse MIDI tracks
    local i, trackId=15, 0
    while i < midiContentLength do
        if string.sub(midiContent, i, i+3) ~= "MTrk" then
            break
        end
        local trackLength       = getValue(midiContent, i+4, i+7)
        local trackNotesCount   = 0
        trackId = trackId + 1
        -- Parse MIDI Events
        local j = i + 8
        local extraOffset = 0
        notes[trackId] = {}
        while j < i + trackLength + 8 do
            local eventOffset, nextPos  = getByteValue(midiContent, j)
            j = nextPos
            local eventType = getValue(midiContent, j, j)
            if math.floor(eventType / 16) == 8 then         -- End of a note
                extraOffset = extraOffset + eventOffset
                j = j + 3
            elseif math.floor(eventType / 16) == 9 then     -- Beginning of a note
                trackNotesCount = trackNotesCount + 1
                notes[trackId][trackNotesCount] = (eventOffset+extraOffset)/midiDeltaTime
                -- print(trackNotesCount, (eventOffset+extraOffset)/midiDeltaTime)
                extraOffset = 0
                j = j + 3
            elseif math.floor(eventType / 16) == 10 then    -- Key after touch
                extraOffset = extraOffset + eventOffset
                j = j + 3
            elseif math.floor(eventType / 16) == 11 then    -- Controller
                extraOffset = extraOffset + eventOffset
                j = j + 3
            elseif math.floor(eventType / 16) == 12 then    -- Change the instrument
                extraOffset = extraOffset + eventOffset
                j = j + 2
            elseif math.floor(eventType / 16) == 13 then    -- Track after touch??
                extraOffset = extraOffset + eventOffset
                j = j + 2
            elseif math.floor(eventType / 16) == 14 then    -- Portamento
                extraOffset = extraOffset + eventOffset
                j = j + 3
            elseif eventType == 240 then        -- System code?
                extraOffset = extraOffset + eventOffset
                local eventLength, nextPos  = getByteValue(midiContent, j+1)
                j = nextPos + eventLength
            elseif eventType == 255 then        -- Information
                local informType                = getValue(midiContent, j+1, j+1)
                local informLength, nextPos = getByteValue(midiContent, j+2)
                if informType == 3 then     -- Track's name
                    trackName = string.sub(midiContent, nextPos, nextPos + informLength - 1)
                elseif informType == 81 then
                    midiTempo   = 60*1000000/getValue(midiContent, nextPos, nextPos+2)
                elseif informType == 88 then
                    beatNum = getValue(midiContent, nextPos  , nextPos  )
                    beatDen = getValue(midiContent, nextPos+1, nextPos+1)
                    beatClk = getValue(midiContent, nextPos+2, nextPos+2)
                    beatCnt = getValue(midiContent, nextPos+3, nextPos+3)
                end
                j = nextPos + informLength
            end
        end
        -- print(trackId,trackName, trackNotesCount)
        i = i + trackLength + 8
    end

    -- Succeeded
    midiFile:close()
    return true
end
function convertFrame(frame, frameRate)
    return frame/frameRate*midiTempo/60
end
function getNoteId(pos, trackId)
    local totalTime = 0
    for i=1,#notes[trackId]-1 do
        totalTime = totalTime + notes[trackId][i]
        if totalTime + notes[trackId][i+1] > pos then
            return i, totalTime
        end
    end
    return #notes[trackId], totalTime+notes[trackId][#notes[trackId]]
end

if videoFile then
    if midiPath then
        parseMidi(midiPath)
        local id, lastTime = getNoteId(convertFrame(obj.frame+2, obj.framerate), tonumber(midiTrack))
        obj.load("movie", videoFile[1], obj.time-lastTime/(midiTempo/60), alpha)
        if id % 2 == 0 then
            if flipH==1 then
                obj.effect("Reversal", "Flip horizontal", 1)
            end
            if flipV==1 then
                obj.effect("Reversal", "Flip vertical", 1)
            end
            if #effects~=0 then
                for i=1,#effects do
                    obj.effect(unpack(effects[i]))
                end
            end
        end
    end
end

目前已知的bug:

  1. 多音符会出现奇怪的效果

  2. 更换midi后无法及时更新画面

Windows 10突然无法启动,开机提示0xc000000e。
按照网上的教程,进PE系统试了下bcdedit,结果提示“无法打开启动配置数据存储。拒绝访问”。再仔细一看,原来网上的教程貌似只适用于Windows 7。
然后找到了一篇Microsoft Community上的讨论:Error code: 0xc000000e in Windows 10
于是做了个安装启动盘,进了命令提示符,执行了Bootrec /fixmbr,成功。接着执行了Bootrec /fixboot,结果提示拒绝访问。
Microsoft Community上又有一篇:Windows 10 bootrec /fixboot access is denied
看了后恍然大悟,原来是EFI分区出了问题。那么修复EFI分区即可:

diskpart
sel disk 0                          // 选择硬盘
list vol                            // 看一下EFI分区的编号
sel vol 4                           // 选择这个EFI分区
assign letter=V:                    // 挂载分区
exit

bcdboot C:\windows /s V: /f UEFI    // 修复EFI分区

如果有必要的话,可以先格式化EFI分区再修复:

format V: /FS:FAT32

使用方法和cin类似,只需要将cin换成xszq::cin即可。

#ifndef IO_H_
#define IO_H_


#if defined(__unix)    \
 || defined(__unix__)  \
 || defined(__linux)   \
 || defined(__linux__)
#define IO_H_VERSION 1.1

#include <unistd.h>
#include <fcntl.h>
#include <sys/mman.h>
#include <cctype>
#include <string>

namespace xszq {
class istream {
public:
    istream();
    istream& operator>>(int&);
    istream& operator>>(int short&);
    istream& operator>>(int long&);
    istream& operator>>(int long long&);
    istream& operator>>(int unsigned&);
    istream& operator>>(int short unsigned&);
    istream& operator>>(int long unsigned&);
    istream& operator>>(int long long unsigned&);
    istream& operator>>(char&);
    istream& operator>>(char unsigned&);
    istream& operator>>(char*);
    istream& operator>>(std::string&);
    operator bool();
private:
    char *ptr;
    char *begin;
    bool lastSuccess;
} cin;

istream::istream() {
    ptr = (char *) mmap(NULL, lseek(0, 0, SEEK_END), PROT_READ, MAP_PRIVATE, 0, 0);
    begin = ptr;
    lastSuccess = true;
}
#define integerUnsignedOperator(type)                          \
istream& istream::operator>>(type& var) {                       \
    var = 0;                                                    \
    while (*ptr && !isdigit(*ptr)) {++ ptr;}                    \
    if (!(*ptr)) {lastSuccess = false; return *this;}           \
    while (*ptr &&  isdigit(*ptr)) {var=var*10+*ptr++-48;}      \
    return *this;                                               \
}
#define integerSignedOperator(type)                                \
istream& istream::operator>>(type& var) {                       \
    bool isNegative = false;                                    \
    var = 0;                                                    \
    while (*ptr && !isdigit(*ptr)) {isNegative|=*ptr++=='-';}   \
    if (!(*ptr)) {lastSuccess = false; return *this;}           \
    while (*ptr &&  isdigit(*ptr)) {var=var*10+*ptr++-48;}      \
    if (isNegative) var = -var;                                 \
    return *this;                                               \
}

integerSignedOperator(int)
integerSignedOperator(int short)
integerSignedOperator(int long)
integerSignedOperator(int long long)
integerUnsignedOperator(int unsigned)
integerUnsignedOperator(int short unsigned)
integerUnsignedOperator(int long unsigned)
integerUnsignedOperator(int long long unsigned)
istream& istream::operator>>(char& var) {
    var = '\0';
    while (*ptr && isspace(*ptr)) {++ ptr;}
    if (!(*ptr)) {lastSuccess = false; return *this;}
    var = *ptr++;
    return *this;
}
istream& istream::operator>>(char unsigned& var) {
    var = '\0';
    while (*ptr && isspace(*ptr)) {++ ptr;}
    if (!(*ptr)) {lastSuccess = false; return *this;}
    var = *ptr++;
    return *this;
}
istream& istream::operator>>(char *var) {
    *var = '\0';
    while (*ptr &&  isspace(*ptr)) {++ ptr;}
    if (!(*ptr)) {lastSuccess = false; return *this;}
    while (*ptr && !isspace(*ptr)) {*var = *ptr; ++ var; ++ ptr;}
    *var = '\0';
    return *this;
}
istream& istream::operator>>(std::string& var) {
    var = "";
    while (*ptr &&  isspace(*ptr)) {++ ptr;}
    if (!(*ptr)) {lastSuccess = false; return *this;}
    while (*ptr && !isspace(*ptr)) {var += *ptr; ++ ptr;}
    return *this;
}
istream::operator bool() {
    return lastSuccess;
}
}
#else
#error "This header file only supports Unix/Linux."
#endif


#endif

dup2函数可以复制文件描述符,从而实现文件重定向。该函数通常可以用来重定向进程的程序的标准输入输出。
该函数原型如下:

int dup2 (int __fd, int __fd2);

如果返回值为-1,则表示重定向失败。
该函数将会把文件描述符__fd2替换为__fd。
下面是一个重定向标准输入输出的简单例子:

#include <unistd.h>
#include <fcntl.h>
int main() {
    int fd1 = open("input.txt", O_RDONLY), fd2 = open("output.txt", O_WRONLY);
    dup2(fd1, STDIN_FILENO);
    dup2(fd2, STDOUT_FILENO);
    return 0;
}

这样就可以把STDIN重定向到文件input.txt,STDOUT重定向到文件output.txt了。
补充一点:如果需要让输出文件自动创建,open函数需要加上O_CREAT标识:

open("output.txt", O_WRONLY | O_CREAT, 0777);

如果需要让文件自动清空,需要加上O_TRUNC标识:

open("output.txt", O_WRONLY | O_TRUNC);

此题显然可以用分块做。我们只需要用分块维护字典序最大的字符串的下标即可。
本人刚学分块,代码可能有不足之处,请见谅。
代码:

#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>

// 计算下标所在的块
#define calc(a) (ceil((double)a/size)>tot?tot:ceil((double)a/size))

using namespace std;
int n, m, tot, size, l[225], r[225], mx[225], x, y;
char o[50001][15];
char s[50001][15];

// 处理询问
int query() {
    // lid、rid分别是左端点和右端点所在的块的编号,ret是答案
    int lid = calc(x), rid = calc(y), ret; 

    // 分情况处理
    if (lid == rid) {
        ret = x;
        for ( int i = x+1; i <= y; ++ i )
            if (strcmp(s[i], s[ret])>=0) // 用strcmp比较字典序
                ret = i;
    } else {
        ret = x;

        // 暴力处理左端
        for ( int i = x+1; i <= r[lid]; ++ i )
            if (strcmp(s[i], s[ret])>=0) // 用strcmp比较字典序
                ret = i;

        // 中间部分
        for ( int i = lid+1; i < rid; ++ i )
            if (strcmp(s[mx[i]], s[ret])>=0) // 用strcmp比较字典序
                ret = mx[i];

        // 暴力处理右端
        for ( int i = l[rid]; i <= y; ++ i )
            if (strcmp(s[i], s[ret])>=0) // 用strcmp比较字典序
                ret = i;
    }
    return ret;
}

// 转换大小写
void convert(char* k) { 
    int len = strlen(k);
    for ( int i = 0; i < len; ++ i )
        k[i] = tolower(k[i]);
}

int main() {
    scanf("%d%d", &n, &m); // 输入数据较大,使用cin输入会TLE

    // 求出块的大小和块的数量
    tot = size = sqrt(n);

    // 输入字符串
    for ( register int i = 1; i <= n; ++ i ) {
        scanf("%s", s[i]);
        memcpy(o[i], s[i], sizeof(s[i])); // 用o数组保存原字符串,s数组保存转换小写后的字符串
        convert(s[i]); // 转换大小写
    }

    // 保存块的左右端点
    for ( register int i = 1; i <= tot; ++ i )
        l[i] = (i-1)*size+1,
        r[i] = i*size;

    // 处理末端多出来的一块
    if (r[tot] < n) {
        ++tot;
        l[tot] = r[tot-1]+1;
        r[tot] = n;
    }

    // 预处理
    for ( register int i = 1; i <= tot; ++ i ) {
        mx[i] = l[i];
        for ( register int j = l[i]+1; j <= r[i]; ++ j )
            if (strcmp(s[j], s[mx[i]])>=0) // 处理块内字典序最大的字符串
                mx[i] = j;
    }

    // 回答询问
    while (m--) {
        scanf("%d%d", &x, &y); // 输入区间
        puts(o[query()]); // 输出答案
    }
    return 0;
}

题目描述
一般的文本编辑器都有查找单词的功能,该功能可以快速定位特定单词在文章中的位置,有的还能统计出特定单词在文章中出现的次数。
现在,请你编程实现这一功能,具体要求是:给定一个单词,请你输出它在给定的文章中出现的次数和第一次出现的位置。注意:匹配单词时,不区分大小写,但要求完全匹配,即给定单词必须与文章中的某一独立单词在不区分大小写的情况下完全相同(参见样例1 ),如果给定单词仅是文章中某一单词的一部分则不算匹配(参见样例2 )。
输入输出格式
输入格式:
共 2 行。第 1 行为一个字符串,其中只含字母,表示给定单词;第 2 行为一个字符串,其中只可能包含字母和空格,表示给定的文章。
输出格式:
一行,如果在文章中找到给定单词则输出两个整数,两个整数之间用一个空格隔开,分别是单词在文章中出现的次数和第一次出现的位置(即在文章中第一次出现时,单词首字母在文章中的位置,位置从 0 开始);如果单词在文章中没有出现,则直接输出一个整数 −1 。

输入输出样例
输入样例#1:
To
to be or not to be is a question
输出样例#1:
2 0

输入样例#2:
to
Did the Ottoman Empire lose its power at that time
输出样例#2:
-1

说明
数据范围
1≤ 单词长度 ≤10 。
1≤ 文章长度 ≤1,000,000 。
NOIp2011普及组第2题。

题解
本题较为简单的解法是逐项对比,同时也可以用Hash解法,这里阐述的即为Hash解法。
注意,测试样例时请自行去除行末的空格,题中已说明行末无空格。

代码

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
typedef unsigned long long ULL;// 把unsigned long long简写
const int b=27;
const int MAXN=1000050;// 数组大小
string t1;// 输入的单词
string t2;// 输入的文章
char s1[MAXN];// 输入的单词
char s2[MAXN];// 输入的文章
long long power[MAXN];// 用来存放b&n
long long sum[MAXN];// 用来存放主串hash值
int main() {
    int i,pos=-1;// 第一次出现的位置,如果没有就是-1
    power[0]=1;// b^0=1
    for (int i=1;i<MAXN;++i)// 计算MAXN次
        power[i]=power[i-1]*b;// 计算b*n
    getline(cin,t1);// 用getline读入一整行
    getline(cin,t2);// 用getline读入一整行
    int s1len=t1.length(),s2len=t2.length();// 存放长度
    for (int i=0;i<s1len;i++) s1[i+1]=tolower(t1[i]);// 放进s1数组并转换大小写,注意这里往后移了一位
    for (int i=0;i<s2len;i++) s2[i+1]=tolower(t2[i]);// 放进s2数组并转换大小写,注意这里往后移了一位
    sum[0]=0;// 初始化
    for (int i=1;i<=s2len;++i)
        sum[i]=sum[i-1]*b+s2[i];// 计算主串hash值
    ULL s=0;// 用来存放子串hash值
    for (int i=1;i<=s1len;++i)
        s=s*b+s1[i];// 计算子串hash值
    int tot=0;// 计数器
    for (int i=0;i<=s2len-s1len;++i)
        if(s==sum[i+s1len]-sum[i]*power[s1len]&&(i==0||s2[i]==' ')&&(i+s1len==s2len||s2[i+s1len+1]==' '))// 如果hash值匹配,并且这个词前后是空格(或者在文章开头/结尾)
        {
            if (pos==-1) pos=i;// 如果是第一个,保存位置
            ++tot;// 总词数加1
        }
    if (pos==-1) cout<<-1;// 没有找到,输出-1
    else cout<<tot<<' '<<pos<<endl;// 输出次数、位置
    return 0;// 结束程序
}