A：折半搜索+二分 跟上星期一樣的知識點
B：拓撲排序
C：里面知識點都經常考并且糅合在一起，非常好的一道題，并查集+樹DP考慮邊的貢獻
D：掃描線 上星期知識點 出這道題是因為可以用bitset暴力卡，可以學習bitset，但是記得補正解
E：思維題 拿來簽到
F：弗洛伊德
G：高斯消元比較模板的題，但是很惡心，卡精度，卡eps不能調太大，而且卡long double
A題
CodeForces - 912E
Opposite to Grisha's nice behavior, Oleg, though he has an entire year at his disposal, didn't manage to learn how to solve number theory problems in the past year. That's why instead of Ded Moroz he was visited by his teammate Andrew, who solemnly presented him with a set of n distinct prime numbers alongside with a simple task: Oleg is to find the k-th smallest integer, such that all its prime divisors are in this set.
Input
The first line contains a single integer n (1?≤?n?≤?16).
The next line lists n distinct prime numbers p1,?p2,?...,?pn (2?≤?pi?≤?100) in ascending order.
The last line gives a single integer k (1?≤?k). It is guaranteed that the k-th smallest integer such that all its prime divisors are in this set does not exceed 1018.
Output
Print a single line featuring the k-th smallest integer. It's guaranteed that the answer doesn't exceed 1018.
Examples
Input
3 2 3 5 7
Output
8
Input
5 3 7 11 13 31 17
Output
93
Note
The list of numbers with all prime divisors inside {2,?3,?5} begins as follows:
(1,?2,?3,?4,?5,?6,?8,?...)
The seventh number in this list (1-indexed) is eight.
知識點和上星期一樣，折半搜索＋二分查找，
主要是一開始讀不懂題，根本不知道是什么意思，試了好久才知道是包括1且因數要包括集合內的元素，
先用DFS列舉好所有狀態的結果，然后兩邊雙指標同時進行，二分列舉目前的mid是排在第幾，直到找到ans為止，
代碼：
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <string.h>
#include <math.h>
#include <cmath>
#include <stack>
#include <queue>
#include <list>
#include <vector>
using namespace std;
const long long oo=1e18;
int k;
int n;
long long p[20];
vector<long long> a[2];
void ready()
{
ios::sync_with_stdio(false),cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
cin>>p[i];
cin>>k;
}
void dfs(int temp,int u,long long now)
{
a[temp].push_back(now);
for(int i=u;i<=n;i+=2)
if(oo/p[i]>=now)
dfs(temp,i,now*p[i]);
}
bool check(long long mid)
{
long long ki=0;
for(int i=(int)a[0].size()-1,j=0;i>=0;i--)
{
while(j<(int)a[1].size() && a[1][j]<=mid/a[0][i])
j++;
ki+=j;
}
return ki>=k;
}
void work()
{
dfs(0,1,1);
dfs(1,2,1);
sort(a[0].begin(),a[0].end());
sort(a[1].begin(),a[1].end());
long long l=1,r=oo,mid=(l+r)/2;
while(l<=r)
{
mid=(l+r)/2;
if(check(mid))
r=mid-1;
else
l=mid+1;
}
cout<<l;
return ;
}
int main()
{
ready();
work();
return 0;
}
B題
CodeForces - 770C
Now you can take online courses in the Berland State University! Polycarp needs to pass k main online courses of his specialty to get a diploma. In total n courses are availiable for the passage.
The situation is complicated by the dependence of online courses, for each course there is a list of those that must be passed before starting this online course (the list can be empty, it means that there is no limitation).
Help Polycarp to pass the least number of courses in total to get the specialty (it means to pass all main and necessary courses). Write a program which prints the order of courses.
Polycarp passes courses consistently, he starts the next course when he finishes the previous one. Each course can't be passed more than once.
Input
The first line contains n and k (1?≤?k?≤?n?≤?105) — the number of online-courses and the number of main courses of Polycarp's specialty.
The second line contains k distinct integers from 1 to n — numbers of main online-courses of Polycarp's specialty.
Then n lines follow, each of them describes the next course: the i-th of them corresponds to the course i. Each line starts from the integer ti (0?≤?ti?≤?n?-?1) — the number of courses on which the i-th depends. Then there follows the sequence of ti distinct integers from 1 to n — numbers of courses in random order, on which the i-th depends. It is guaranteed that no course can depend on itself.
It is guaranteed that the sum of all values ti doesn't exceed 105.
Output
Print -1, if there is no the way to get a specialty.
Otherwise, in the first line print the integer m — the minimum number of online-courses which it is necessary to pass to get a specialty. In the second line print m distinct integers — numbers of courses which it is necessary to pass in the chronological order of their passage. If there are several answers it is allowed to print any of them.
Examples
Input
6 2 5 3 0 0 0 2 2 1 1 4 1 5
Output
5 1 2 3 4 5
Input
9 3 3 9 5 0 0 3 9 4 5 0 0 1 8 1 6 1 2 2 1 2
Output
6 1 2 9 4 5 3
Input
3 3 1 2 3 1 2 1 3 1 1
Output
-1
Note
In the first test firstly you can take courses number 1 and 2, after that you can take the course number 4, then you can take the course number 5, which is the main. After that you have to take only the course number 3, which is the last not passed main course.
雖說是拓撲排序，但我感覺更像是思維DFS，主要在記錄狀態的時候注意一下，好吧就是記錄狀態這里要做好就行了，就是個普普通通的DFS，
保存狀態和最后存進ans在DFS最后儲存，這樣能保證先儲存的就是最里面的點，這個地方卡了我好久，比賽的時候就是卡在這個地方了，
注意要反方向構圖！
代碼：
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <string.h>
#include <math.h>
#include <cmath>
#include <stack>
#include <queue>
#include <list>
#include <vector>
using namespace std;
int n,k;
int p[100005],nex[100005],to[100005],pi;
int ki[100005];
int ans[100005],ansi;
bool q[100005];
int f[100005];
int cnt[100005];
bool ANS;
struct B{
int id;
int in_;
}t[100005];
void read_in(int u,int v)
{
pi++;nex[pi]=p[u];p[u]=pi;to[pi]=v;
}
bool cmp(B i,B j)
{
return i.in_<j.in_;
}
void ready()
{
ios::sync_with_stdio(false),cin.tie(0);
cin>>n>>k;
for(int i=1;i<=k;i++)
cin>>ki[i];
for(int i=1;i<=n;i++)
{
int ti;
cin>>ti;
while(ti--)
{
int vi;
cin>>vi;
read_in(i,vi);
}
}
}
void dfs(int u)
{
f[u]=-1;
for(int i=p[u],v=to[i];i;i=nex[i],v=to[i])
{
if(f[v]==-1)
{
ANS=true;
return ;
}
if(!f[v])
dfs(v);
}
f[u]=1;
ans[++ansi]=u;
}
void work()
{
for(int i=1;i<=k;i++)
{
if(!f[ki[i]])
dfs(ki[i]);
if(ANS)
{
cout<<-1;
return ;
}
}
cout<<ansi<<'\n';
for(int i=1;i<=ansi;i++)
cout<<ans[i]<<' ';
return ;
}
int main()
{
ready();
work();
return 0;
}
/*
5 3
2 1 3
0
1 1
1 2
0
0
*/
E題
CodeForces - 1186C
Vus the Cossack has two binary strings, that is, strings that consist only of "0" and "1". We call these strings aa and bb. It is known that |b|≤|a||b|≤|a|, that is, the length of bb is at most the length of aa.
The Cossack considers every substring of length |b||b| in string aa. Let's call this substring cc. He matches the corresponding characters in bb and cc, after which he counts the number of positions where the two strings are different. We call this function f(b,c)f(b,c).
For example, let b=00110b=00110, and c=11000c=11000. In these strings, the first, second, third and fourth positions are different.
Vus the Cossack counts the number of such substrings cc such that f(b,c)f(b,c) is even.
For example, let a=01100010a=01100010 and b=00110b=00110. aa has four substrings of the length |b||b|: 0110001100, 1100011000, 1000110001, 0001000010.
- f(00110,01100)=2f(00110,01100)=2;
- f(00110,11000)=4f(00110,11000)=4;
- f(00110,10001)=4f(00110,10001)=4;
- f(00110,00010)=1f(00110,00010)=1.
Since in three substrings, f(b,c)f(b,c) is even, the answer is 33.
Vus can not find the answer for big strings. That is why he is asking you to help him.
Input
The first line contains a binary string aa (1≤|a|≤1061≤|a|≤106) — the first string.
The second line contains a binary string bb (1≤|b|≤|a|1≤|b|≤|a|) — the second string.
Output
Print one number — the answer.
Examples
Input
01100010 00110
Output
3
Input
1010111110 0110
Output
4
Note
The first example is explained in the legend.
In the second example, there are five substrings that satisfy us: 10101010, 01010101, 11111111, 11111111.
思維題，吃在了看不懂題的虧，不知道even是偶數的意思，也沒去猜f（b，c）到底是什么意思，
題意也就是兩串01組成的字串a，b，|a| >= |b| ，在a中取 |b| 長度，和b異或后如果1的個數為偶數則這是一個目標子串，問a中有多少個長度為|b|且滿足條件的子串，
思維題，找規律，7爺比完之后立刻和我說這肯定cf的題目，
如果兩個子串中，1的個數同為偶數或者同為奇數，則不管1在不在同一個位置，異或之后剩下的1肯定都是偶數，所以用前綴和維護就好，
代碼
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <string.h>
#include <math.h>
#include <cmath>
#include <stack>
#include <queue>
#include <list>
#include <vector>
using namespace std;
string a,b;
int la,lb,ai[1000006],bi[1000006],ans;
void ready()
{
ios::sync_with_stdio(false),cin.tie(0);
cin>>a>>b;
la=a.size();lb=b.size();
for(int i=0;i<la;i++)
if(i==0)
ai[i]=a[i]-'0';
else
ai[i]=ai[i-1]+a[i]-'0';
for(int i=0;i<lb;i++)
if(i==0)
bi[i]=b[i]-'0';
else
bi[i]=bi[i-1]+b[i]-'0';
}
int check_(int x,int y)
{
if(x%2==y%2)
return 1;
else
return 0;
}
int main()
{
ready();
for(int i=lb-1;i<la;i++)
{
if(i==lb-1)
ans+=check_(bi[lb-1],ai[i]);
else
ans+=check_(bi[lb-1],ai[i]-ai[i-lb]);
}
cout<<ans;
return 0;
}
F題
CodeForces - 33B
Boy Valera likes strings. And even more he likes them, when they are identical. That's why in his spare time Valera plays the following game. He takes any two strings, consisting of lower case Latin letters, and tries to make them identical. According to the game rules, with each move Valera can change one arbitrary character Ai in one of the strings into arbitrary character Bi, but he has to pay for every move a particular sum of money, equal to Wi. He is allowed to make as many moves as he needs. Since Valera is a very economical boy and never wastes his money, he asked you, an experienced programmer, to help him answer the question: what minimum amount of money should Valera have to get identical strings.
Input
The first input line contains two initial non-empty strings s and t, consisting of lower case Latin letters. The length of each string doesn't exceed 105. The following line contains integer n (0?≤?n?≤?500) — amount of possible changings. Then follow n lines, each containing characters Ai and Bi (lower case Latin letters) and integer Wi (0?≤?Wi?≤?100), saying that it's allowed to change character Ai into character Bi in any of the strings and spend sum of money Wi.
Output
If the answer exists, output the answer to the problem, and the resulting string. Otherwise output -1 in the only line. If the answer is not unique, output any.
Examples
Input
uayd uxxd 3 a x 8 x y 13 d c 3
Output
21 uxyd
Input
a b 3 a b 2 a b 3 b a 5
Output
2 b
Input
abc ab 6 a b 4 a b 7 b a 8 c b 11 c a 3 a c 0
Output
-1
題意：有n種替換字母的方式，將兩個只包括小寫字母的字串替換成相同字串所需要的最少錢是多少，結果字串是什么，
一開始以為直接逐位比較變成對方就OK了，然后發現可能可以同時變為第三個字母，然后加了個跳板一起變成第三個，然后想想，可以構造一個圖，用Floyd來做，兩個字母之間有轉換也就是有路，費用就是權值，Floyd就能找到兩個之間轉換到哪個字母比較好，花錢比較少，后面就簡單了，
代碼：
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <string.h>
#include <math.h>
#include <cmath>
#include <stack>
#include <queue>
#include <list>
#include <vector>
using namespace std;
string a,b;
long long val[30][30];
int len_a,len_b,n;
long long money;
char ans[100005];
void ready()
{
ios::sync_with_stdio(false),cin.tie(0);
cin>>a>>b>>n;
len_a=a.size();
len_b=b.size();
for(int i=1;i<=26;i++)
for(int j=1;j<=26;j++)
val[i][j]=1000000000;
for(int i=1;i<=n;i++)
{
char x,y;
long long v;
cin>>x>>y>>v;
val[x-'a'+1][y-'a'+1]=min(val[x-'a'+1][y-'a'+1],v);
}
for(int i=1;i<=26;i++)
val[i][i]=0;
for(int k=1;k<=26;k++)
for(int i=1;i<=26;i++)
for(int j=1;j<=26;j++)
val[i][j]=min(val[i][j],val[i][k]+val[k][j]);
}
bool work()
{
if(len_a!=len_b)
return false;
for(int i=0;i<len_a;i++)
{
if(a[i]!=b[i])
{
long long cost=1000000000,ci;
int ai=a[i]-'a'+1;
int bi=b[i]-'a'+1;
for(int j=1;j<=26;j++)
{
if(val[ai][j]+val[bi][j]<cost)
{
cost=val[ai][j]+val[bi][j];
ci=j;
}
}
if(cost==1000000000)
return false;
money+=cost;
ans[i]=char('a'+ci-1);
}
else
{
ans[i]=a[i];
}
}
cout<<money<<'\n';
for(int i=0;i<len_a;i++)
cout<<ans[i];
return true;
}
int main()
{
ready();
if(!work())
cout<<-1;
return 0;
}
G題
Gym - 100962A
Problem A. ABBA Input file: standard input Output file: standard output Time limit: 1 second Memory limit: 256 mebibytes In this problem, we operate with tables of fixed size h × w consisting of real values. Let’s define an addition operation on two tables as their component-wise sum. A multiplication table for two real vectors α = (α1, α2, . . . , αh) and β = (β1, β2 . . . , βw) is the table Tα,β where the element at the intersection of i-th row and j-th column is αi · βj . You start with a table of size h × w consisting of zeroes. In one turn, you are allowed to add a multiplication table for two arbitrary real vectors α of length h and β of length w to the current table. Your task is to make the current table equal to a goal table G in the minimum number of turns. What is the minimum number of turns you have to perform? Input The first line of input contains two integers h and w (1 ≤ h, w ≤ 200). The i-th of the following h lines contain w space-separated integers ai,1, ai,2, . . . , ai,w (?106 ≤ ai,j ≤ 106 ), where ai,j is the value on the intersection of i-th row and j-th column of the goal table G. Output If it’s impossible to obtain the goal table G, print “-1” (without the quotes). Otherwise, output the minimum number of turns you have to perform in order to achieve it. Examples standard input standard output 3 5 1 2 3 4 5 2 4 6 8 10 3 6 9 12 15 1 3 3 2 0 2 0 2 0 2 0 2 2 Note In the first sample, the table T can be obtained using α = ( 1 2 3) , β = ( 1 2 3 4 5) . In the second sample, the table T can be obtained as sum of Tα1,β1 = ? ? 1 1 1 1 1 1 1 1 1 ? ? for vectors α1 = ( 1 1 1) , β1 = ( 1 1 1) and Tα2,β2 = ? ? 1 ?1 1 ?1 1 ?1 1 ?1 1 ? ? for vectors α2 = ( ?1 1 ?1 ) , β2 = ( ?1 1 ?1 )
題意：求矩陣的秩，
身為一個數學與應用數學專業的學生，高等代數上學期也學了，高斯消元法求矩陣的秩也是我們平常的做法，上學期高代學得不錯，專業第5，但是這道題看不懂題根本不知道再求秩......
而且以前不敢寫高斯消元法的代碼就是怕經度問題，現在打出來了，剛剛好可以用行程式設計的課程設計里，nice！
高斯消元法，也就是湊1消去后面的項，直到形成上三角矩陣，
代碼：
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <string.h>
#include <math.h>
#include <cmath>
#include <stack>
#include <queue>
#include <list>
#include <vector>
using namespace std;
const long double ep=1e-2;
long double a[205][205];
int r,c;
void ready()
{
ios::sync_with_stdio(false),cin.tie(0);
cin>>r>>c;
for(int i=1;i<=r;i++)
for(int j=1;j<=c;j++)
cin>>a[i][j];
}
void work()
{
int row=1,col=1;
for( ;row<=r && col<=c;row++,col++)
{
int max_r=row;
for(int i=row+1;i<=r;i++)
if(abs(a[i][col])>abs(a[max_r][col]))
max_r=i;
if(max_r!=row)
for(int i=row;i<=c;i++)
swap(a[row][i],a[max_r][i]);
if(abs(a[row][col])<ep)
{
row--;
continue;
}
for(int i=row+1;i<=r;i++)
if(abs(a[i][col])>ep)
{
double t=a[i][col]/a[row][col];
for(int j=row;j<=c;j++)
a[i][j]-=t*a[row][j];
}
}
cout<<row-1;
}
int main()
{
ready();
work();
return 0;
}
好好學英語，下次帶字典去了，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/283184.html
標籤：其他
上一篇：原來Linux大神都是這么記住命令的，看看你們的方法是否一樣。
下一篇：不知道何時，我逐漸喪失了表達能力