#1626 : 缩写命名




时间限制:10000ms
单点时限:1000ms
内存限制:256MB



描述
很多计算机科学工作者都喜欢给自己发明的系统或者方法起个拉风的名字。他们一般会用若干个单词描述这个系统，并且从这些单词中各取出一个字母组合在一起作为系统的名字。如果组合在一起的名字恰好是个有意义的单词，那就更COOL了。  
例如 "FAWN:a Fast Array of Wimpy Nodes"
 以及 "EMILI: Energy Minimizing Idle Listening wIfi"。
现在给定一个包含N个单词的字典{W1, W2,
 ... WN}和一个目标单词S，能否从字典中选出|S|个不同的单词，并且从每个单词中取出一个字母组成单词S？

输入
输入包含多组数据。
第一行包含一个整数T，代表测试数据的组数。(1 ≤ T ≤ 20)  
对于每组数据，第一行包含一个整数N。  
第二行包含目标单词S。  
以下N行每行一个单词Wi。  
对于30%的数据，1 ≤ N ≤ 10  
对于100%的数据，1 ≤ N ≤ 100, 1 ≤ |S| ≤ 100, 1 ≤ |Wi| ≤ 100, 所有单词只包含小写字母。

输出
对于每组数据，输出一行Yes或者No，代表是否能通过上述方法组成S。


样例输入
2  
4  
hiho
oh  
i  
hate  
you
3    
hiho
happy  
input
output

样例输出
Yes  
No




裸的模板题，建图、匈牙利算法，二分图匹配。。。。WA到死，一直得0分，赛后检查代码，发现YES和NO我都大写了，题目要求小写。。。。。有毒啊










#include <iostream>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <bits/stdc++.h>
using namespace std;

int T,N;
string S;
int V;
vector<int>G[209];
int match[209];
bool used[209];
bool haveEdge[109][109];
void addEdge(int a,int b){
    G[a].push_back(b);
    G[b].push_back(a);
}

bool dfs(int v){
    used[v]=1;
    for(int i=0;i<G[v].size();i++){
        int u=G[v][i];
        int w=match[u];
        if(w<0||!used[w]&&dfs(w)){
            match[v]=u;
            match[u]=v;
            return 1;
        }
    }
    return 0;
}

int bipartite_matching(){
    int res=0;
    memset(match,-1,sizeof(match));
    for(int i=0;i<V;i++){
        if(match[i]<0){
            memset(used,0,sizeof(used));
            if(dfs(i))res++;
        }
    }
    return res;
}


int main(){
    cin>>T;
    while(T--){
        cin>>N;
        cin>>S;
        int Len=S.length();
        V=Len+N;
        for(int i=0;i<V;i++){
            G[i].clear();
        }
        memset(haveEdge,0,sizeof(haveEdge));
        for(int i=0;i<N;i++){
            string W;
            cin>>W;
            for(int j=0;j<W.length();j++){
                for(int k=0;k<Len;k++){
                    if(S[k]==W[j]){
                        if(!haveEdge[k][Len+i]){
                            addEdge(k,Len+i);
                            haveEdge[k][Len+i]=1;
                        }
                    }
                }
            }
        }
        if(bipartite_matching()==Len)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;


    }
    return 0;
}

//
//                       _oo0oo_
//                      o8888888o
//                      88" . "88
//                      (| -_- |)
//                      0\  =  /0
//                    ___/`---'\___
//                  .' \\|     |// '.
//                 / \\|||  :  |||// \
//                / _||||| -:- |||||- \
//               |   | \\\  -  /// |   |
//               | \_|  ''\---/''  |_/ |
//               \  .-\__  '-'  ___/-. /
//             ___'. .'  /--.--\  `. .'___
//          ."" '<  `.___\_<|>_/___.' >' "".
//         | | :  `- \`.;`\ _ /`;.`/ - ` : | |
//         \  \ `_.   \_ __\ /__ _/   .-` /  /
//     =====`-.____`.___ \_____/___.-`___.-'=====
//                       `=---='
//
//
//     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
//
//               佛祖保佑         永无BUG
//
//
//

名词解释

PWM 是 Pulse Width Modulation 的缩写，它的中文名字是脉冲宽度调制，它利用微处理器的数字输出来对模拟电路进行控制，其实就是使用数字信号达到一个模拟信号的效果。

首先从它的名字来看，脉冲宽度调制，就是改变脉冲宽度来实现不同的效果。我们先来看三组不同的脉冲信号，如图 10-1 所示。 

图片来源于c语言中文网


  
这是一个周期是 10ms，即频率是 100Hz 的波形，但是每个周期内，高低电平脉冲宽度各不相同，这就是 PWM 的本质。在这里大家要记住一个概念，叫做“占空比”。占空比是指高电平的时间占整个周期的比例。比如第一部分波形的占空比是 40%，第二部分波形占空比是 60%，第三部分波形占空比是 80%，这就是 PWM 的解释。
  
  
如果我们把这个间隔不断的减小，减小到我们的肉眼分辨不出来，也就是 100Hz 以上的频率，这个时候小灯表现出来的现象就是既保持亮的状态，但亮度又没有 LED = 0;时的亮度高。那我们不断改变时间参数，让 LED = 0;的时间大于或者小于 LED = 1;的时间，会发现亮度都不一样，这就是模拟电路的感觉了，不再是纯粹的 0 和 1，还有亮度不断变化。




函数解释

1.使用 RPI.GPIO 模块的脉宽调制（PWM）功能

创建一个 PWM 实例：


  
p = GPIO.PWM(channel, frequency) 


启用 PWM：


  
p.start(dc)    # dc 代表占空比（范围：0.0 <= dc >= 100.0）


更改频率：


  
p.ChangeFrequency(freq)    # freq 为设置的新频率，单位为 Hz


更改占空比：


  
p.ChangeDutyCycle(dc)   # 范围：0.0 <= dc >= 100.0


停止 PWM：


  
p.stop()


注意，如果实例中的变量“p”超出范围，也会导致 PWM 停止。

代码示例

以下为使 LED 每两秒钟闪烁一次的示例：

import RPi.GPIO as GPIO
GPIO.setmode(GPIO.BOARD)
GPIO.setup(12, GPIO.OUT)

p = GPIO.PWM(12, 0.5)
p.start(1)
input('点击回车停止：')   # 在 Python 2 中需要使用 raw_input
p.stop()
GPIO.cleanup()

以下为使 LED 在亮/暗之间切换的示例：



import time
import RPi.GPIO as GPIO
GPIO.setmode(GPIO.BOARD)
GPIO.setup(12, GPIO.OUT)

p = GPIO.PWM(12, 50)  # 通道为 12 频率为 50Hz
p.start(0)
try:
    while 1:
        for dc in range(0, 101, 5):
            p.ChangeDutyCycle(dc)
            time.sleep(0.1)
        for dc in range(100, -1, -5):
            p.ChangeDutyCycle(dc)
            time.sleep(0.1)
except KeyboardInterrupt:
    pass
p.stop()
GPIO.cleanup()

	

PWM是Pulse Width Modulation的缩写，它的中文名字是脉冲宽度调制，一种说法是它利用微处理器的数字输出来对模拟电路进行控制的一种有效的技术，其实就是使用数字信号达到一个模拟信号的效果。这是个什么概念呢？我们一步步来介绍。首先从它的名字来看，脉冲宽度调制，就是改变脉冲宽度来实现不同的效果。我们先来看三组不同的脉冲信号，如图所示。图 PWM 波形这是一个周期是 10ms，即频率是 100Hz 的波形，但是每个周期内，高低电平脉冲宽度各不相同，这就是 PWM 的本质。在这里大家要记住一个概念，叫做“占空比”。占空比是指高电平的时间占整个周期的比例。比如第一部分波形的占空比是 40%，第二部分波形占空比是 60%，第三部分波形占空比是 80%，这就是 PWM 的解释。那为何它能对模拟电路进行控制呢？大家想一想，我们数字电路里，只有 0 和 1 两种状态，比如我们第 2 章学会的点亮 LED 小灯那个程序，当我们写一个 LED = 0;小灯就会长亮，当我们写一个 LED = 1;小灯就会灭掉。当我们让小灯亮和灭间隔运行的时候，小灯是闪烁。如果我们把这个间隔不断的减小，减小到我们的肉眼分辨不出来，也就是 100Hz 以上的频率，这个时候小灯表现出来的现象就是既保持亮的状态，但亮度又没有 LED = 0;时的亮度高。那我们不断改变时间参数，让 LED = 0;的时间大于或者小于 LED = 1;的时间，会发现亮度都不一样，这就是模拟电路的感觉了，不再是纯粹的 0 和 1，还有亮度不断变化。大家会发现，如果我们用 100Hz 的信号，如图 10-1 所示，假如高电平熄灭小灯，低电平点亮小灯的话，第一部分波形熄灭 4ms，点亮 6ms，亮度最高，第二部分熄灭 6ms，点亮 4ms，亮度次之，第三部分熄灭 8ms，点亮 2ms，亮度最低。那么用程序验证一下我们的理论，我们用定时器T0 定时改变 P0.0 的输出来实现 PWM，与纯定时不同的是，这里我们每周期内都要重载两次定时器初值，即用两个不同的初值来控制高低电平的不同持续时间。为了使亮度的变化更加明显，程序中使用的占空比差距更大。
#includesbit PWMOUT = P0^0;sbit ADDR0 = P1^0;sbit ADDR1 = P1^1;sbit ADDR2 = P1^2;sbit ADDR3 = P1^3;sbit ENLED = P1^4;unsigned char HighRH = 0; //高电平重载值的高字节unsigned char HighRL = 0; //高电平重载值的低字节unsigned char LowRH = 0; //低电平重载值的高字节unsigned char LowRL = 0; //低电平重载值的低字节void ConfigPWM(unsigned int fr, unsigned char dc);void ClosePWM();void main(){unsigned int i;EA = 1; //开总中断ENLED = 0; //使能独立 LEDADDR3 = 1;ADDR2 = 1;ADDR1 = 1;ADDR0 = 0;while (1){ConfigPWM(100, 10); //频率 100Hz，占空比 10%for (i=0; i40000; i++);ClosePWM();ConfigPWM(100, 40); //频率 100Hz，占空比 40%for (i=0; i40000; i++);ClosePWM();ConfigPWM(100, 90); //频率 100Hz，占空比 90%for (i=0; i40000; i++);ClosePWM(); //关闭 PWM，相当于占空比 100%for (i=0; i40000; i++);}}/* 配置并启动 PWM，fr-频率，dc-占空比 */void ConfigPWM(unsigned int fr, unsigned char dc){unsigned int high, low;unsigned long tmp;tmp = (11059200/12) / fr; //计算一个周期所需的计数值high = (tmp*dc) / 100; //计算高电平所需的计数值low = tmp - high; //计算低电平所需的计数值high = 65536 - high + 12; //计算高电平的重载值并补偿中断延时low = 65536 - low + 12;//计算低电平的重载值并补偿中断延时HighRH = (unsigned char)(high>>8); //高电平重载值拆分为高低字节HighRL = (unsigned char)high;LowRH = (unsigned char)(low>>8); //低电平重载值拆分为高低字节LowRL = (unsigned char)low;TMOD &= 0xF0; //清零 T0 的控制位TMOD |= 0x01; //配置 T0 为模式 1TH0 = HighRH; //加载 T0 重载值TL0 = HighRL;ET0 = 1; //使能 T0 中断TR0 = 1; //启动 T0PWMOUT = 1; //输出高电平}/* 关闭 PWM */void ClosePWM(){TR0 = 0; //停止定时器ET0 = 0; //禁止中断PWMOUT = 1; //输出高电平}/* T0 中断服务函数，产生 PWM 输出 */void InterruptTimer0() interrupt 1{if (PWMOUT == 1){ //当前输出为高电平时，装载低电平值并输出低电平TH0 = LowRH;TL0 = LowRL;PWMOUT = 0;}else{ //当前输出为低电平时，装载高电平值并输出高电平TH0 = HighRH;TL0 = HighRL;PWMOUT = 1;}}
需要提醒大家的是，由于标准 51 单片机中没有专门的 PWM 模块，所以我们用定时器加中断的方式来产生 PWM，而现在有很多的单片机都会集成硬件的 PWM 模块，这种情况下需要我们做的就仅仅是计算一下周期计数值和占空比计数值然后配置到相关的 SFR 中即可，既使程序得到了简化又确保了 PWM 的输出品质(因为消除了中断延时的影响)。大家编译下载程序后，会发现小灯从最亮到灭一共 4 个亮度等级。如果我们让亮度等级更多，并且让亮度等级连续起来，会产生一个小灯渐变的效果，与呼吸有点类似，所以我们习惯上称之为呼吸灯，程序代码如下，这个程序用了 2 个定时器 2 个中断，这是我们第一次这样用，大家可以学习一下。我们来试试这个程序，试完了大家一定要能自己把程序写出来，切记。
#includesbit PWMOUT = P0^0;sbit ADDR0 = P1^0;sbit ADDR1 = P1^1;sbit ADDR2 = P1^2;sbit ADDR3 = P1^3;sbit ENLED = P1^4;unsigned long PeriodCnt = 0; //PWM 周期计数值unsigned char HighRH = 0; //高电平重载值的高字节unsigned char HighRL = 0; //高电平重载值的低字节unsigned char LowRH = 0; //低电平重载值的高字节unsigned char LowRL = 0; //低电平重载值的低字节unsigned char T1RH = 0; //T1 重载值的高字节unsigned char T1RL = 0; //T1 重载值的低字节void ConfigTimer1(unsigned int ms);void ConfigPWM(unsigned int fr, unsigned char dc);void main(){EA = 1; //开总中断ENLED = 0; //使能独立 LEDADDR3 = 1;ADDR2 = 1;ADDR1 = 1;ADDR0 = 0;ConfigPWM(100, 10); //配置并启动 PWMConfigTimer1(50); //用 T1 定时调整占空比while (1);}/* 配置并启动 T1，ms-定时时间 */void ConfigTimer1(unsigned int ms){unsigned long tmp; //临时变量tmp = 11059200 / 12; //定时器计数频率tmp = (tmp * ms) / 1000; //计算所需的计数值tmp = 65536 - tmp; //计算定时器重载值tmp = tmp + 12; //补偿中断响应延时造成的误差T1RH = (unsigned char)(tmp>>8); //定时器重载值拆分为高低字节T1RL = (unsigned char)tmp;TMOD &= 0x0F; //清零 T1 的控制位TMOD |= 0x10; //配置 T1 为模式 1TH1 = T1RH; //加载 T1 重载值TL1 = T1RL;ET1 = 1; //使能 T1 中断TR1 = 1; //启动 T1}/* 配置并启动 PWM，fr-频率，dc-占空比 */void ConfigPWM(unsigned int fr, unsigned char dc){unsigned int high, low;PeriodCnt = (11059200/12) / fr; //计算一个周期所需的计数值high = (PeriodCnt*dc) / 100; //计算高电平所需的计数值low = PeriodCnt - high; //计算低电平所需的计数值high = 65536 - high + 12; //计算高电平的定时器重载值并补偿中断延时low = 65536 - low + 12; //计算低电平的定时器重载值并补偿中断延时HighRH = (unsigned char)(high>>8); //高电平重载值拆分为高低字节HighRL = (unsigned char)high;LowRH = (unsigned char)(low>>8); //低电平重载值拆分为高低字节LowRL = (unsigned char)low;TMOD &= 0xF0; //清零 T0 的控制位TMOD |= 0x01; //配置 T0 为模式 1TH0 = HighRH; //加载 T0 重载值TL0 = HighRL;ET0 = 1; //使能 T0 中断TR0 = 1; //启动 T0PWMOUT = 1; //输出高电平}/* 占空比调整函数，频率不变只调整占空比 */void AdjustDutyCycle(unsigned char dc){unsigned int high, low;high = (PeriodCnt*dc) / 100; //计算高电平所需的计数值low = PeriodCnt - high; //计算低电平所需的计数值high = 65536 - high + 12; //计算高电平的定时器重载值并补偿中断延时low = 65536 - low + 12; //计算低电平的定时器重载值并补偿中断延时HighRH = (unsigned char)(high>>8); //高电平重载值拆分为高低字节HighRL = (unsigned char)high;LowRH = (unsigned char)(low>>8); //低电平重载值拆分为高低字节LowRL = (unsigned char)low;}/* T0 中断服务函数，产生 PWM 输出 */void InterruptTimer0() interrupt 1{if (PWMOUT == 1){ //当前输出为高电平时，装载低电平值并输出低电平TH0 = LowRH;TL0 = LowRL;PWMOUT = 0;}else{ //当前输出为低电平时，装载高电平值并输出高电平TH0 = HighRH;TL0 = HighRL;PWMOUT = 1;}}/* T1 中断服务函数，定时动态调整占空比 */void InterruptTimer1() interrupt 3{static bit dir = 0;static unsigned char index = 0;unsigned char code table[13] = { //占空比调整表5, 18, 30, 41, 51, 60, 68, 75, 81, 86, 90, 93, 95};TH1 = T1RH; //重新加载 T1 重载值TL1 = T1RL;AdjustDutyCycle(table[index]); //调整 PWM 的占空比if (dir == 0){ //逐步增大占空比index++;if (index >= 12){dir = 1;}}else{ //逐步减小占空比index--;if (index == 0){dir = 0;}}}
呼吸灯效果做出来后，利用这个基本原理，其它各种效果的灯光闪烁都应该可以做出来，大家看到的 KTV 里边那绚丽的灯光闪烁，其实就是采用的 PWM 技术控制的。

一．POI简介 

Jakarta POI 是apache的子项目，目标是处理ole2对象。它提供了一组操纵Windows文档的Java API 

目前比较成熟的是HSSF接口，处理MS Excel（97-2002）对象。它不象我们仅仅是用csv生成的没有格式的可以由Excel转换的东西，而是真正的Excel对象，你可以控制一些属性如sheet,cell等等。 

二．HSSF概况 

HSSF 是Horrible SpreadSheet Format的缩写，也即“讨厌的电子表格格式”。 也许HSSF的名字有点滑稽，就本质而言它是一个非常严肃、正规的API。通过HSSF，你可以用纯Java代码来读取、写入、修改Excel文件。 

HSSF 为读取操作提供了两类API：usermodel和eventusermodel，即“用户模型”和“事件-用户模型”。前者很好理解，后者比较抽象，但操作效率要高得多。 

三．开始编码 

1 ． 准备工作 

要求:JDK 1.4+POI开发包 

可以到 http://www.apache.org/dyn/closer.cgi/jakarta/poi/ 最新的POI工具包 

2 ． EXCEL 结构 

HSSFWorkbook excell 文档对象介绍 
HSSFSheet excell的表单 
HSSFRow excell的行 
HSSFCell excell的格子单元 
HSSFFont excell字体 
HSSFName 名称 
HSSFDataFormat 日期格式 
在poi1.7中才有以下2项： 
HSSFHeader sheet头 
HSSFFooter sheet尾 
和这个样式 
HSSFCellStyle cell样式 
辅助操作包括 
HSSFDateUtil 日期 
HSSFPrintSetup 打印 
HSSFErrorConstants 错误信息表 

3 ．具体用法实例 （采用 usermodel ） 

如何读Excel 

读取Excel文件时，首先生成一个POIFSFileSystem对象，由POIFSFileSystem对象构造一个HSSFWorkbook，该HSSFWorkbook对象就代表了Excel文档。下面代码读取上面生成的Excel文件写入的消息字串：


Java代码 

POIFSFileSystem fs=newPOIFSFileSystem(new FileInputStream("d:/test.xls"));    
HSSFWorkbook 　wb = new HSSFWorkbook(fs);    
　　} catch (IOException e) {    
　　e.printStackTrace();    
　　}    
　　HSSFSheet sheet = wb.getSheetAt(0);    
　　HSSFRow row = sheet.getRow(0);    
　　HSSFCell cell = row.getCell((short) 0);    
　　String msg = cell.getStringCellValue();   

POIFSFileSystem fs=newPOIFSFileSystem(new FileInputStream("d:/test.xls")); 
HSSFWorkbook 　wb = new HSSFWorkbook(fs); 
　　} catch (IOException e) { 
　　e.printStackTrace(); 
　　} 
　　HSSFSheet sheet = wb.getSheetAt(0); 
　　HSSFRow row = sheet.getRow(0); 
　　HSSFCell cell = row.getCell((short) 0); 
　　String msg = cell.getStringCellValue(); 


如何写excel， 

将excel的第一个表单第一行的第一个单元格的值写成“a test”。


Java代码 

POIFSFileSystem fs =new POIFSFileSystem(new FileInputStream("workbook.xls"));    
  
    HSSFWorkbook wb = new HSSFWorkbook(fs);    
  
    HSSFSheet sheet = wb.getSheetAt(0);    
  
    HSSFRow row = sheet.getRow(0);    
  
    HSSFCell cell = row.getCell((short)0);    
  
    cell.setCellValue("a test");    
  
    // Write the output to a file    
  
    FileOutputStream fileOut = new FileOutputStream("workbook.xls");    
  
    wb.write(fileOut);    
  
fileOut.close();   

POIFSFileSystem fs =new POIFSFileSystem(new FileInputStream("workbook.xls")); 

    HSSFWorkbook wb = new HSSFWorkbook(fs); 

    HSSFSheet sheet = wb.getSheetAt(0); 

    HSSFRow row = sheet.getRow(0); 

    HSSFCell cell = row.getCell((short)0); 

    cell.setCellValue("a test"); 

    // Write the output to a file 

    FileOutputStream fileOut = new FileOutputStream("workbook.xls"); 

    wb.write(fileOut); 

fileOut.close(); 


4 ． 可参考文档 

POI 主页：http://jakarta.apache.org/poi/， 

初学者如何快速上手使用POI HSSF 

http://jakarta.apache.org/poi/hssf/quick-guide.html 。 

代码例子 http://blog.java-cn.com/user1/6749/archives/2005/18347.html 


里面有很多例子代码，可以很方便上手。 

四．使用心得 

POI HSSF 的usermodel包把Excel文件映射成我们熟悉的结构，诸如Workbook、Sheet、Row、Cell等，它把整个结构以一组对象的形式保存在内存之中，便于理解，操作方便，基本上能够满足我们的要求，所以说这个一个不错的选择。