3058: 小明爱集合

开始想的是对输入进行排序之后用二分查找的方法找到数据或者插入位置，代码如下:

#include <iostream>
#include <math.h>
#include <vector>
using namespace std;

inline bool scan_d(int &num)
{
    char in;bool IsN=false;
    in=getchar();
    if(in==EOF) return false;
    while(in!='-'&&(in<'0'||in>'9')) in=getchar();
    if(in=='-'){ IsN=true;num=0;}
    else num=in-'0';
    while(in=getchar(),in>='0'&&in<='9'){
        num*=10,num+=in-'0';
    }
    if(IsN) num=-num;
    return true;
}

vector<int>::iterator find(vector<int> &num, int a, bool &flag)
{
    if(a < num.front())
    {
        return num.begin();
    }
    if(a > num.back())
    {
        return num.end();
    }
    int left = 0, right = num.size();
    int mid = 0;
    while(left <= right)
    {
        mid = (left + right) / 2;
        if(a < num.at(mid))
            right = mid - 1;
        else if(a > num.at(mid))
            left = mid + 1;
        else{
            flag = true;
            return num.begin() + mid;
        }
    }
    return num.begin() + right + 1;
}

int main() {
    int T;
    scan_d(T);
    vector<int> result;
    for(int t=0; t < T; t++)
    {
        int m, n;
        scan_d(m);
        scan_d(n);
        vector<int> array_m;
        for(int i = 0; i < m; i++)
        {
            int temp = 0;
//            cin >> temp;
            scan_d(temp);
            array_m.push_back(temp);
        }
        sort(array_m.begin(), array_m.end());
        int same = 0;
        for(int i = 0; i < n; i++)
        {
            int temp;
//            cin >> temp;
            scan_d(temp);
            bool flag = false;
            vector<int>::iterator it = find(array_m, temp, flag);
            if(flag)
            {
                same = same + 1;
                array_m.erase(it);
            }
            else
            {
                array_m.insert(it, temp);
            }
        }
        int percent = same * 100 / (same + array_m.size());
        result.push_back(percent);
    }
    for(int i = 0; i < T; i++)
    {
        cout << result[i] << endl;
    }
    return 0;
}

但是这个方法后面会超时。仔细看数据范围：

第一行包括两个数n,m，分别表示两个集合元素的个数(1<=n,m<100000)；
第二行n个数表示前一集合的n个数，以空格隔开；
第三行m个数表示后一集合的m个数，以空格隔开；
其中对于两集合中任意数ai，有0<=ai<=max(2n,2m)。

感觉可以直接用map

#include <iostream>
#include <math.h>
#include <vector>
#include <map>
using namespace std;

inline bool scan_d(int &num)
{
    char in;bool IsN=false;
    in=getchar();
    if(in==EOF) return false;
    while(in!='-'&&(in<'0'||in>'9')) in=getchar();
    if(in=='-'){ IsN=true;num=0;}
    else num=in-'0';
    while(in=getchar(),in>='0'&&in<='9'){
        num*=10,num+=in-'0';
    }
    if(IsN) num=-num;
    return true;
}

int main() {
    int T;
    scan_d(T);
    vector<int> result;
    for(int t=0; t < T; t++)
    {
        int m, n;
        scan_d(m);
        scan_d(n);
        map<int, int> array;
        for(int i = 0; i < m; i++)
        {
            int temp;
            scan_d(temp);
            array[temp] = 1;
        }
        int same = 0;
        for(int i = 0; i < n; i++)
        {
            int temp;
            scan_d(temp);
            if(array.count(temp))
                same = same + 1;
            else
                array[temp] = 1;
        }
        int percent = same * 100 / (m + n - same);
        result.push_back(percent);
    }
    for(int i = 0; i < T; i++)
    {
        cout << result[i] << endl;
    }
    return 0;
}

驱动开发环境

碎碎念

网速慢搭环境真的太苦了......主要记录几个错误的地方

WindowsDriver.common.targets(460,5): error MSB6004: The specified task executable location "\stampinf.exe" is invalid.
我感觉是因为SDK版本和WDK版本不统一导致的，查看WDK和SDK版本:

所以在项目中需要都选择16299这个版本:
编译报错：LNK2019 无法解析的外部符号 DriverEntry
文件名称应该是.c而不是.cpp
WindowsDriver.common.targets（1373,5）：错误MSB4018 ：“SignTask”任务意外失败
解决方案中，选择工程右键，选择“属性”，在配置属性中选择“Driver Signing”，将 “Sign mode” 修改为 “Off”

测试

#include "ntddk.h"

VOID DriverUnload(PDRIVER_OBJECT DriverObject)
{
    if (DriverObject != NULL)
    {
        DbgPrint("[%ws]Driver Upload, Driver Object Address:%p", __FUNCTIONW__, DriverObject);

    }
    return;
}

NTSTATUS DriverEntry(PDRIVER_OBJECT DriverObject, PUNICODE_STRING RegisterPath)
{
    DbgPrint("[%ws]Hello Kernel World\n", __FUNCTIONW__);
    if (RegisterPath != NULL)
    {
        DbgPrint("[%ws]Driver RegisterPath:%wZ\n", __FUNCTIONW__, RegisterPath);
    }
    if (DriverObject != NULL)
    {
        DbgPrint("[%ws]Driver Object Address:%p\n", __FUNCTIONW__, DriverObject);
        DriverObject->DriverUnload = DriverUnload;
    }
    return STATUS_SUCCESS;
}

关闭Windows驱动签名：开始 -> 设置 -> 更新与安全 -> 恢复；立即重启；疑难解答 -> 高级选项 -> 启动设置 -> 重启；选7: 禁用驱动程序强制签名
创建服务并启动

sc create FirstDriver binPath= "C:\Users\ep\Desktop\Driver\MyDriver1.sys" type= kernel start= demand
sc start FirstDriver

使用DebugView查看，勾选上“监视核心”与“启动详细核心输出”选项

驱动调试

设置被调试机器

将被调试机器设置乘调试模式，并开启网络调试端口

bcdedit /debug on
bcdedit /dbgsettings net hostip:调试机ip port:50010

输入第二条命令的时候会出现一个密钥key，需要保存这个密钥

设置调试机器

VS -> Driver -> Test -> Configure Devices
Add New Device:

hostname中填的是被调试机器的ip
下一步:

hostip是调试机器的ip，key是之前生成的密钥

开始调试

首先使用KdBreakPoint函数设置断点。

#include "ntddk.h"

VOID DriverUnload(PDRIVER_OBJECT DriverObject)
{
    if (DriverObject != NULL)
    {
        DbgPrint("[%ws]Driver Upload, Driver Object Address:%p", __FUNCTIONW__, DriverObject);

    }
    return;
}

NTSTATUS DriverEntry(PDRIVER_OBJECT DriverObject, PUNICODE_STRING RegisterPath)
{
    KdBreakPoint();
    DbgPrint("[%ws]Hello Kernel World\n", __FUNCTIONW__);
    if (RegisterPath != NULL)
    {
        DbgPrint("[%ws]Driver RegisterPath:%wZ\n", __FUNCTIONW__, RegisterPath);
    }
    if (DriverObject != NULL)
    {
        DbgPrint("[%ws]Driver Object Address:%p\n", __FUNCTIONW__, DriverObject);
        DriverObject->DriverUnload = DriverUnload;
    }
    return STATUS_SUCCESS;
}

然后进行编译生成sys驱动文件。
选择调试 -> 附加到进程 -> 连接类型: Windows Kernel Mode Debugger, 连接目标是刚才配置生成的ep，可用进程选择"kenel"
单击“附加”之后“Debugger Immediate Window"界面会显示