next_permutation
ABC054
next_permutationを使う問題。
int main(){
int n, m, a[30], b[30], c[10], ans=0;
cin >> n >> m;
for(int i=0; i<m; i++){
cin >> a[i] >> b[i];
}
for(int i=0; i<n; i++){
c[i]=i+1;
}
bool flag;
do{
if(c[0]==1){
for(int i=0; i<n-1; i++){
for(int j=0; j<m; j++){
flag=false;
if(c[i]==a[j] && c[i+1]==b[j] || c[i]==b[j] && c[i+1]==a[j]){
flag=true;
break;
}
}
if(!flag){
break;
}
}
if(flag){
ans++;
}
}
}while(next_permutation(c, c+n));
cout << ans << endl;
return 0;
}
覚えておきたい。
ユークリッドの互除法
これ以上でもこれ以下でもなく、普通にユークリッドの互除法(Euclidean Algorithm)で最大公約数(greatest common divisor)を求めるだけ
int gcd(int a, int b){
int c;
if(a<b){
a+=b;
b=a-b;
a-=b;
}
while(b!=0){
c=a%b;
a=b;
b=c;
}
return a;
}
substrとunique
- substr
substrを使うと部分文字列が取得できる。
s.substr(i, j); i番目の要素からj要素だけ部分文字列を取り出す。
string s = "ABCDEFG";
s.substr(2, 3); →CDE
- unique
uniqueを使うと隣接する重複した要素をなくせる。要素をなくしてもvectorの長さは変わらないから末尾になんか残る。なのでsortしてからuniqueしてその後にeraseで削除してあげるのが最善らしい。
vector<int> vec = {1, 4, 4, 2, 2, 3, 2, 2, 4};
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
memset関数
memset関数を使うとメモリに指定バイト数分の値をセットできる。
#include<cstring>
memset(void *buf, int ch, size_t n);
void *buf; セット先のメモリブロック
int ch; セットする文字
size_t n; セットバイト数
例
bool dp[110][10010];
memset(dp, 0, sizeof(dp));
これでdpにfalseをセットできる。
sizeof(dp)で配列のサイズが返ってくるらしい。
pair
pairをしっかり使えるようになりたいね。
typedef pair<int, int> P;
int a=1, b=2, c=3, d=4;
P x, y;
x=P(a, b);
y=P(c, d);
cout << x.first << " " << x.second << endl;
cout << y.first << " " << y.second << endl;
実行結果
1 2
3 4
重要
reverseだけするとバグるっぽいからsort→reverseってしましょう。
優先順位付きのキュー
#include<queue>
using namespace std;
priority_queue<int> maxpq;
priority_queue<int, vector<int>, greater<int> > minpq;
デフォルトでは大きい順にpop, 小さい順にするには, greaterを宣言時に書く.
要素の追加
pq.push(1);
先頭の要素を取り出す
pq.pop(); // 最大or最小の先頭を取り出す
要素を調べる
pq.empty(); // 要素数が0ならtrue, それ以外ではfalseを返す
pq.size(); // 要素数を調べる
pq.top(); // 次に取り出される要素を調べる.
知ってると使えるは全然違うことを何度も言いたい。
それにしてもABC90のC問題、出力の仕方間違えてるの最後まで気づかずに終わってしまったのは悔しい。悔しいなあ・・・
精進するぞ。
