1004 Tokitsukaze and Multiple
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6794

题意：含有n个数的序列，相邻的数可以相加成为一个新的数，问最后最多能有多少个数是p的倍数

思路：用set就特别简单，我们现在set里插入0，再用个变量t来表示每个数ai mod p,如果这个t已经存在set里，则说明已经有一个数是p的倍数ans++（因为一个数加上p的倍数再mod p 肯定还是这个数，或者这个数本来就是p的倍数），并将set清空且重新插入0,否则将t插入，直至遍历完。 

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
typedef long long ll;
using namespace std;
int a[100005];
set<int> f;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T; cin >> T;
    while(T--)
    {
        int n,p;cin >> n>>p;
        for(int i=1;i<=n;i++)
        {
            cin >> a[i];
        }
        f.clear();f.insert(0);
        int ans=0,t=0;
        for(int i=1;i<=n;i++)
        {
            t+=a[i]%p;
            t=t%p;
            if(f.count(t))
            {
                ans++;
                t=0;
                f.clear();f.insert(0);
            }
            f.insert(t);
        }
        cout << ans << endl;
     } 
    return 0;
 } 

1009 Parentheses Matching

题意：一个字符串由三种字符 ‘*'、'('、 ')' 组成，我们可以将’*‘替换成其它任意两个或这空字符，如果能使替换后的字符串平衡（例如："", "()", "(())", "()()", "()(())"），输出字典序最小的结果，否则输出No solution!。

思路：比赛的时候没想出来，单纯的匹配还是不难，难就难到还要求字典序最小，看了下组里其他人a了后的代码，其实就贪心一下，尽可能在最左边变成左括号，在最右边变成右括号，最后需要判断是否满足匹配的字符串即可。我们可以用一个数组来记录一下*的位置，优先使用最前面的。 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char st[100020];
int to[100020];
void solve(int len){
  int tmp=0;
  for(int i=1;i<=len;i++){
    if(st[i]=='(') tmp++;
    else if(st[i]==')') {
      tmp--;
      if(tmp<0) break;
    }
  }
  if(tmp==0){
    for(int i=1;i<=len;i++){
      if(st[i]!='*') cout<<st[i];
    }
    cout<<endl;
  }
  else{
    puts("No solution!");
  }
}
int main()
{
    int t;
    cin>>t;
    while(t--){
      scanf("%s",st+1);
      int len =strlen(st+1);
      int id=0,pre=0,tmp=0;
      for(int i=0;i<=len;i++) to[i]=0; //别用memset,效率太慢，这道题会超时
      for(int i=1;i<=len;i++){
        if(st[i]=='(')   tmp++;
        else if(st[i]==')'){
          tmp--;
          if(tmp<0){
           if(to[id]==0) break;
           id=to[id];
           st[id]='(';
           tmp=0;
          }
        }
        else to[pre]=i,pre=i;
      }
      if(tmp>0){
        for(int i=len;i>=1;i--){
          if(st[i]=='*') st[i]=')',tmp--;
          if(tmp==0) break;
        }
      }
      solve(len);
    }
}