201509-1 数列分段
水，记下前一个数，看看跟当前是否一样，不一样就ans+1
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath> using namespace std; int n, a; int main() {
// freopen("in", "r", stdin);
while(~scanf("%d", &n)) {
scanf("%d", &a);
int cur = a, cnt = ;
for(int i = ; i < n; i++) {
scanf("%d", &a);
if(cur != a) {
cnt++;
cur = a;
}
}
printf("%d\n", cnt);
}
return ;
}
1
201509-2 日期计算
打表，注意细节就行
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath> using namespace std; const int com[] = {,,,,,,,,,,,, };
const int lep[] = {,,,,,,,,,,,, };
int y, c, m, d; int main() {
// freopen("in", "r", stdin);
while(~scanf("%d %d", &y, &c)) {
d = ;
if((y % == && y % != ) || (y % == )) {
for(int i = ; i <= ; i++) {
if(lep[i] < c) {
m = i;
}
else break;
}
d = c - lep[m];
m++;
if(d != ) printf("%d\n%d\n", m, d);
else printf("%d\n%d\n", m, lep[m]-lep[m-]);
}
else {
for(int i = ; i <= ; i++) {
if(com[i] < c) {
m = i;
}
else break;
}
d = c - com[m];
m++;
if(d != ) printf("%d\n%d\n", m, d);
else printf("%d\n%d\n", m, com[m]-com[m-]);
}
}
return ;
}
2
201509-3 模版生成系统
字符串大模拟，无耻地大量使用了STL，甚至出现了vector<pair<vector<int>,vector<int> > >这样的结构。思路就是首先定位此行输入的字符串的需要替换的变量起止位置，再记录当前字符串。接下来读取模式串的键值，放到set中。接下来替换。要注意使用string中的replace时候会让字符串长度发生变化，这时候只要从末尾开始匹配，最后再输出就行了。
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath> using namespace std;
typedef vector<int>::iterator it;
typedef vector<vector<int> >::iterator iit;
typedef pair<vector<int>,vector<int> > pvv;
const int maxn = ; int n, m;
vector<int> start, end;
vector<pvv> sig;
vector<string> str;
map<string, string> var;
char tmp[maxn]; int main() {
// freopen("in", "r", stdin);
while(~scanf("%d %d", &m, &n)) {
sig.clear();
var.clear();
getchar();
for(int i = ; i < m; i++) {
start.clear();
end.clear();
gets(tmp);
int len = strlen(tmp);
for(int j = ; j < len; j++) {
if(tmp[j] == ' ' && tmp[j-] == '{' && tmp[j-] == '{') start.push_back(j+);
if(tmp[j] == ' ' && tmp[j+] == '}' && tmp[j+] == '}') end.push_back(j-);
}
sig.push_back(pvv(start, end));
str.push_back(string(tmp));
}
for(int i = ; i < n; i++) {
gets(tmp);
string raw(tmp);
int j;
for(j = ; j < raw.length(); j++) {
if(raw[j] == ' ') break;
}
var[raw.substr(, j)] = raw.substr(j+, raw.length()-j-);
}
for(int i = ; i < sig.size(); i++) {
if(sig[i].first.empty()) {
printf("%s\n", str[i].c_str());
continue;
}
for(int j = sig[i].first.size() - ; j >= ; j--) {
str[i].replace(
sig[i].first[j]-, sig[i].second[j]-sig[i].first[j]+,
var[str[i].substr(sig[i].first[j], sig[i].second[j]-sig[i].first[j]+)]);
// cout << sig[i].first[j] << " " << sig[i].second[j] << endl;
// cout << str[i].substr(sig[i].first[j], sig[i].second[j]-sig[i].first[j] + 1) << endl;
}
printf("%s\n", str[i].c_str());
}
}
return ;
}
3
201509-4 高速公路
求多少个连通对。先tarjan跑出所有连通分量，然后枚举任意两个不相等的点，看看是否属于同一个连通分量里。
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath> using namespace std; const int maxn = ;
const int maxm = ;
typedef struct Edge {
int u;
int v;
int next;
Edge() { next = -; }
}Edge; int head[maxn], ecnt;
Edge edge[maxm];
int n, m; int bcnt, dindex;
int dfn[maxn], low[maxn];
int stk[maxn], top;
int belong[maxn];
bool instk[maxn]; void init() {
memset(edge, , sizeof(edge));
memset(head, -, sizeof(head));
memset(instk, , sizeof(instk));
memset(dfn, , sizeof(dfn));
memset(low, , sizeof(low));
memset(belong, , sizeof(belong));
ecnt = top = bcnt = dindex = ;
} void adde(int uu, int vv) {
edge[ecnt].u = uu;
edge[ecnt].v = vv;
edge[ecnt].next = head[uu];
head[uu] = ecnt++;
} void tarjan(int u) {
int v = u;
dfn[u] = low[u] = ++dindex;
stk[++top] = u;
instk[u] = ;
for(int i = head[u]; ~i; i=edge[i].next) {
v = edge[i].v;
if(!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if(instk[v] && dfn[v] < low[u]) {
low[u] = dfn[v];
}
}
if(dfn[u] == low[u]) {
bcnt++;
do {
v = stk[top--];
instk[v] = ;
belong[v] = bcnt;
} while(v != u);
}
} int main() {
// freopen("in", "r", stdin);
int uu, vv;
while(~scanf("%d %d", &n, &m)) {
init();
for(int i = ; i < m; i++) {
scanf("%d %d", &uu, &vv);
adde(uu, vv);
}
for(uu = ; uu <= n; uu++) {
if(!dfn[uu]) {
tarjan(uu);
}
}
int ans = ;
for(int i = ; i <= n; i++) {
for(int j = i + ; j <= n; j++) {
if(belong[i] == belong[j]) {
ans++;
}
}
}
printf("%d\n", ans);
}
return ;
}
4